Seminár z teórie grafov - Róbert Jajcay (10.4.2025)
vo štvrtok 10.4.2025 o 9:50 hod. v miestnosti M 213
Prednášajúci: Róbert Jajcay
Názov: Classification and Extremal Properties of Graphs Sharing Properties of Vertex- and/or Edge-Transitive Graphs
Termín: 10.4.2025, 9:50 hod., M 213
Abstrakt:
While many problems in Graph Theory do not require the graphs considered to be vertex- or edge- transitive, ultimately, some of the best constructions yield graphs that just `happen' to have these properties. We choose to address this observation in a 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 {\em 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 {\em 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 {\em 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 {\em vertex-girth-regular}, $vgr(k,g,\Sigma)$, if the {\em 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.