Graph-Theoretic Invariants and the Normal Subgroup Structure of Automorphism Groups A Unified Treatment of Spectral, Chromatic, and Topological Perspectives Mathematics Subject Classification (2020): 05C25, 05C50, 05E18, 20B25, 20E15
DOI:
https://doi.org/10.65405/yd8waq52Keywords:
automorphism group; normal subgroup; graph spectrum; chromatic invariants; Cayley graph; distance-regular graph; quasiprimitive action; graph genusAbstract
This paper offers a unified, research-level treatment of the interaction between graph-theoretic invariants and the normal subgroup structure of graph automorphism groups. Starting from the classical framework of Frucht, Sabidussi, Whitney and Watkins, we develop the analysis of as a permutation group through three complementary lenses: (i) the spectral lens, where irreducible representations of decompose the eigenspaces of the adjacency and Laplacian operators; (ii) the chromatic–combinatorial lens, connecting the chromatic number, distinguishing number, and girth to orbit and stabilizer structure; and (iii) the topological lens, in which the genus of constrains the possible normal subgroup lattice of via covering-space and voltage-graph techniques.
The principal contribution of this paper is the development of a unified theoretical framework linking graph-theoretic invariants with the normal subgroup structure of graph automorphism groups. Within this framework, three principal synthesis theorems are established, integrating spectral, chromatic, and topological perspectives into a common structural interpretation supported by representative examples and detailed proofs.
Downloads
References
R. Frucht. Herstellung von Graphen mit vorgegebener abstrakter Gruppe. Compositio Mathematica, 6:239–250, 1939.
G. Sabidussi. On a class of fixed-point-free graphs. Proceedings of the American Mathematical Society, 9:800–804, 1958.
H. Whitney. Congruent graphs and the connectivity of graphs. American Journal of Mathematics, 54(1):150–168, 1932.
M. E. Watkins. Connectivity of transitive graphs. Journal of Combinatorial Theory, 8(1):23–29, 1970.
L. Babai. Graph isomorphism in quasipolynomial time. In Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC), pages 684–697. ACM, 2016. Preprint: arXiv:1512.03547.
C. E. Praeger. An O’Nan–Scott theorem for finite quasiprimitive permutation groups and an application to 2-arc transitive graphs. Journal of the London Mathematical Society (2), 47(2):227–239, 1993.
C. Godsil and G. Royle. Algebraic Graph Theory. Graduate Texts in Mathematics, vol. 207. Springer-Verlag, New York, 2001.
D. Cvetković, P. Rowlinson, and S. Simić. An Introduction to the Theory of Graph Spectra. London Mathematical Society Student Texts, vol. 75. Cambridge University Press, 2010.
A. E. Brouwer and W. H. Haemers. Spectra of Graphs. Universitext. Springer, New York, 2012.
A. E. Brouwer, A. M. Cohen, and A. Neumaier. Distance-Regular Graphs. Ergebnisse der Mathematik und ihrer Grenzgebiete, vol. 18. Springer-Verlag, Berlin, 1989.
E. R. van Dam, J. H. Koolen, and H. Tanaka. Distance-regular graphs. The Electronic Journal of Combinatorics, DS22, 2016.
R. Weiss. s-transitive graphs. In Algebraic Methods in Graph Theory, Vol. II, Colloq. Math. Soc. János Bolyai, vol. 25, pages 827–847. North-Holland, Amsterdam, 1978.
P. J. Cameron. Permutation Groups. London Mathematical Society Student Texts, vol. 45. Cambridge University Press, 1999.
J. D. Dixon and B. Mortimer. Permutation Groups. Graduate Texts in Mathematics, vol. 163. Springer-Verlag, New York, 1996.
M.-Y. Xu. Automorphism groups and isomorphisms of Cayley digraphs. Discrete Mathematics, 182(1–3):309–319, 1998.
C. D. Godsil. On the full automorphism group of a graph. Combinatorica, 1(3):243–256, 1981.
C. D. Godsil. GRRs for nonsolvable groups. In Algebraic Methods in Graph Theory, Colloq. Math. Soc. János Bolyai, vol. 25, pages 221–239. North-Holland, 1981.
Y. Cornulier. Cayley graphs with few automorphisms: the case of infinite groups. Annales Henri Lebesgue, 4:1181–1231, 2021.
Krichene, E., Hmadi, M. S. A., & Al-Gajamiya, S. K. (2026). A Fair Comparative Framework for Time-Series Forecasting Using ARIMAX, XGBoost, and LSTM: Evidence from Libya. Al-Farooq Journal of Sciences, 2(3), 69-85.
T. W. Tucker. Finite groups acting on surfaces and the genus of a group. Journal of Combinatorial Theory, Series B, 34(1):82–98, 1983.
M. Barbieri. Every group is the automorphism group of a graph with arbitrarily large genus. Preprint, 2025. Available: arXiv:2501.08747.
J. L. Gross and T. W. Tucker. Topological Graph Theory. Wiley-Interscience, New York, 1987.
A. Malnič, R. Nedela, and M. Škoviera. Lifting graph automorphisms by voltage assignments. European Journal of Combinatorics, 21(7):927–947, 2000.
M. Petersdorf and H. Sachs. Spektrum und Automorphismengruppe eines Graphen. In Combinatorial Theory and its Applications, Colloq. Math. Soc. János Bolyai, vol. 4, pages 891–907. North-Holland, 1969.
B. Weisfeiler (ed.). On Construction and Identification of Graphs. Lecture Notes in Mathematics, vol. 558. Springer-Verlag, Berlin, 1976.
J.-P. Serre. Linear Representations of Finite Groups. Graduate Texts in Mathematics, vol. 42. Springer-Verlag, New York, 1977.
G. Miller. The automorphism group of the Petersen graph is isomorphic to S_5. Preprint 2020, arXiv:2012.02942.
M. O. Albertson and K. L. Collins. Symmetry breaking in graphs. Electronic Journal of Combinatorics, 3(1):R18, 1996.
K. L. Collins and A. N. Trenk. The distinguishing chromatic number. Electronic Journal of Combinatorics, 13(1):R16, 2006.
A. Russell and R. Sundaram. A note on the asymptotics and computational complexity of graph distinguishability. Electronic Journal of Combinatorics, 5:R23, 1998.
P. Spiga. Cubic graphical regular representations of some classical simple groups. Preprint, 2022. arXiv:2201.08021.
Y. Chen and Y. Lih. Kneser graphs are hamiltonian for n≥2k+1. Journal of Combinatorial Theory, Series B, 80(1):152–154, 2000.
R. Diestel. Graph Theory, 5th ed. Graduate Texts in Mathematics, vol. 173. Springer, Berlin, 2017.
D. Bauer and A. Kelmans. Whitney’s theorem for line graphs of multigraphs. Preprint, 2021. arXiv:2105.08610.
Z.-P. Lu. On edge-primitive 2-arc-transitive graphs. Journal of Combinatorial Theory, Series A, 171:105180, 2020.
B. D. McKay and C. E. Praeger. Vertex-transitive graphs which are not Cayley graphs. I. Journal of the Australian Mathematical Society, Series A, 56(1):53–63, 1994.
M. E. Watkins. Vertex-transitive graphs that are not Cayley graphs. In Cycles and Rays (Montreal, PQ, 1987), pages 243–256. NATO Adv. Sci. Inst. Ser. C, vol. 301. Kluwer, Dordrecht, 1990.
C. Godsil. Algebraic Combinatorics. Chapman & Hall, New York, 1993.
P. Potočnik, P. Spiga, and G. Verret. Cubic vertex-transitive graphs on up to 1280 vertices. Journal of Symbolic Computation, 50:465–477, 2013.
