Generalizations of Cages and Symmetric Graphs via Girth-Cycle Counting
Ponente: Róbert Jajcay
Institución: Comenius University
Tipo de Evento: Investigación
Institución: Comenius University
Tipo de Evento: Investigación
| Cuándo |
05/11/2025 de 17:00 a 18:00 |
|---|---|
| Dónde | ZOOM ID 675 648 7475, código de acceso: V2hgZi!! |
| Agregar evento al calendario |
vCal
iCal
|
While many problems in Graph Theory do not require the graphsconsidered to be vertex- or edge- transitive, ultimately, someof the best constructions yield graphs that just `happen' tohave these properties. We choose to address this observation ina reverse direction in the context of the Cage and Degree/Diameter Problems, two of the fundamental problems in Extremal Graph Theory, and focus on classes of extremal graphs that are not necessarily vertex- or edge-transitive but share the girth-cycle structure properties of vertex-transitive or edge-transitive graphs.
After a brief survey of the role of vertex-transitive graphs in these areas, we introduce three interconnected concepts sharing the properties of vertex- or edge-transitive graphs: edge-girth regular, girth-regular, and vertex-girth-regular graphs. All of these concept can be best understood via the unifying concept of the girth-cycle signature defined for each vertex u to be the multi-set containing the numbers of girth-cycles passing through the edges adjacent to u. Using this concept, a k-regular graph of girth g, a (k,g)-graph, is called edge-girth-regular egr(k,g,lambda)-graph, if the girth-cycle signature of each vertex is the same and the number of girth-cycles through each edge is equal to a constant lambda. A (k,g)-graph is called girth-regular if the girth-cycle signature of each vertex is the same (without requiring all the members of the signature to be the same), and is called vertex-girth-regular, vgr(k,g,Sigma), if the sum of the numbers in the girth-cycle signature of each vertex is the same and equal to Sigma. Clearly, each edge-girth-regular graph is girth-regular and each girth-regular graph is vertex-girth-regular (with none of the classes equal). In addition, vertex-transitive graphs are necessarily girth- and vertex-girth-regular and edge-transitive graphs are edge-girth-regular.
In view of the connections of the above defined classes of graphs to the Cage and Degree/Diameter Problems, we shall present some classifications for small parameter sets k, g, lambda, and Sigma, and investigate the extremal properties of graphs in these classes.
In view of the connections of the above defined classes of graphs to the Cage and Degree/Diameter Problems, we shall present some classifications for small parameter sets k, g, lambda, and Sigma, and investigate the extremal properties of graphs in these classes.
