On the coherent configurations of some trees

Articles in Press

Document Type : Research Paper

Author

Department of Mathematics education, Faculty of science, Farhangian University, P.O. Box 14665-889,Tehran, Iran

Abstract

This paper investigates the relationship between coherent configurations of graphs and those of their automorphism groups, with a special focus on tree structures. For Schurian coherent configurations—those derived from permutation group orbitals—we establish an isomorphism between the coherent configuration of a graph and that of its automorphism group. We systematically classify the coherent configurations for three fundamental classes of trees: paths, star graphs, and spoke graphs, along with their generalized spoke variants. Through direct product and direct sum operations, we decompose these configurations into combinations of trivial and discrete coherent configurations. A detailed non-trivial example illustrates the coherent configuration of a spoke graph. This work advances the combinatorial analysis of tree symmetries and provides tools for broader graph family classifications, contributing to frameworks for studying graph isomorphism problems and quantum automorphism groups.

Keywords

Main Subjects

References

[1] G. Chen and I. Ponomarenko, Coherent configurations. Central China Normal University Press: 2019. Updated version available online: http://www.pdmi.ras.ru/ inp/ccNOTES.pdf
[2] G. Chen and I. Ponomarenko, Tensor products of coherent configurations. Front. Math. 17 (2022), 829–852.
[3] S. Evdokimov and I. Ponomarenko, Permutation group approach to association schemes. European J. Combin. 30  (2009), 1456–1476.
[4] S. Evdokimov, I. Ponomarenko, and G. Tinhofer, Forestal algebras and algebraic forests (on a new class of weakly compact graphs). Discrete Math. 225 (2000), 149–172.
[5] I. Ponomarenko, On the WL-dimension of circulant graphs of prime power order. Algebraic Combinatorics 6(6) (2023), 1469–1490. DOI:10.5802/alco.315. Available online: https://alco.centre-mersenne.org/articles/10.5802/alco.315/
[6] F. Raei Barandagh and A. Rahnama, On the rank of p-schemes. Electron J Combin. 20 (2013), 30. DOI:10.37236/3097. https://doi.org/10.37236/3097
[7] F. Raei Barandagh, A. Rahnama, On coherent configuration of circular-arc graphs. Communications in Combinatorics and Optimization 10 (2025), 1–19. https://doi.org/10.22049/CCO.2023.28816.1735
[8] B. Weisfeiler, On construction and identification of graphs. Springer Lecture Notes, New York. 558 (1976).
[9] P. H. Zieschang, Theory of association schemes. Springer Monograph in Mathematics, Springer, Berlin, 2005.
Journal of Hyperstructures

Articles in Press, Accepted Manuscript
Available Online from 07 July 2026

Files

Share

How to cite

Statistics