Algebraic Graph Theory Seminar - Eze Leonard Chidiebere (4.10.2024)
Friday 4.10.2024 at 13:15, Lecture room VIII (online too)
Eze Leonard Chidiebere:
Theoretical nad Computational Approaches to Determining Sets of Orders of (k,g)-Graphs
Abstract:
In this talk, we address the problem of determining the set of possible orders for (k, g)-graphs, which play a fundamental role in the study of the Cage Problem in extremal graph theory. For each pair of parameters k ≥ 3 and g ≥ 3, the complete set of orders of (k, g)-graphs is referred to as the spectrum of orders for the (k, g)-graphs, simply written as (k, g)-spectrum. We integrate theoretical insights with computational techniques to determine both complete and partial spectra of orders for several classes of (k, g)-graphs, including cubic, tetravalent, and pentavalent graphs. Our approach utilizes various construction methods, such as edge and vertex deletion, circulant constructions, and generalized Petersen graphs, to systematically expand the known spectra, particularly for graphs with larger girths. Key results include the successful determination of complete spectra for several parameter sets, as well as notable progress in identifying missing elements in others. We also discuss the challenges associated with determining (k, g)-spectra for higher values of k and g, and propose future directions for extending the study to highly symmetric (k, g)-graphs, such as vertex-transitive and Cayley graphs.
[1] L. C. Eze, R. Jajcay and D. Mihalova, An algorithmic approach to determining spectra of orders of (k, g)-graphs, ITAT 2023 Proceedings, CEUR Workshop Proceedings Vol. 3498 (2023) 204 - 208
[2] R. Jajcay and T. Raiman: Spectra of Orders for k-Regular Graphs of Girth g. Discussiones Mathematicae Graph Theory, 41(4) (2021) 1115–1125. https://doi.org/10.7151/dmgt.2233
Those of you who are not able to attend in person or who are still uncertain about the safety of attending in person are welcome to attend via MS Teams. In either case, we hope to see as many of you as possible (either in person or virtually) at our Friday gatherings.