Seminár z teórie grafov - Tatiana Jajcayová (5.12.2024)
vo štvrtok 5.12.2024 o 9:50 hod. v miestnosti M 213
Prednášajúci: Tatiana Jajcayová
Názov: Totally regular mixed cages
Termín: 5.12.2024, 9:50 hod., M 213
Abstrakt:
In our talk, we will discuss a generalization of the original Cage Problem in the setting of mixed graphs. General mixed graphs contain both edges and darts, but the mixed graphs we concentrate on are called totally regular mixed graphs and are graphs in which the number of adjacent non-oriented edges is equal to r, and the number of out-going and in-going darts is equal to z, for all vertices of the graph. The oriented girth g of a mixed graph is the length of a shortest oriented cycle (i.e., a cycle not containing darts of opposing directions). In this context, an (r,z;g)-mixed graph is a totally regular mixed graph in which each vertex of the graph is incident to r edges, z in-going and z out-going darts, and which is of oriented girth g.
In analogy to the Cage Problem, we aim to determine the orders of the smallest totally regular (r,z;g)-mixed graphs, for given parameters r,z and g. We derive several upper and lower bounds on the orders of such minimal graphs and study the relations between these extremal graphs and their non-oriented or digraphical counterparts. We focus on properties of totally regular mixed graphs obtained by replacing some of the edges of the CD(n,q) graphs of Lazebnik, Ustimenko and Woldar and the incidence graphs of projective and biaffine planes by darts. The main aim of this part of our talk is on introducing darts in a way that increases the original non-oriented girths of graphs from these families. We also introduce two constructions based on introducing additional edges or darts into induced subgraphs of the two classes of incidence graphs.
The presented results have been obtained in collaboration with R. Jajcay, Gy. Kiss and I. Porupsanszki.