Schedule for: 23w5125 - Extremal Graphs arising from Designs and Configurations

A $k$-regular graph of girth $g$ is is said to be a $(k,g)$-cage if its order $n(k,g)$ is the smallest among the orders of all $k$-regular graphs of girth $g$. The Cage Problem is the problem of finding cages and the corresponding values $n(k,g)$, for all parameter pairs $k$ and $g$. Cages are only known for very limited sets of parameter pairs, and progress in Cage Problem is unfortunately quite slow. The aim of the presentation is to outline specific problems and questions concerning cages that appear to be particularly suitable for the use of algebraic methods. Notably, a significant proportion of the known cages exhibit a high level of symmetry; with many being vertex-transitive or even Cayley. This observation is the motivation behind restricting the general Cage Problem to the problem of finding smallest vertex-transitive graphs of given degree and girth. While focusing on vertex-transitive graphs may not necessarily directly lead to finding new cages, understanding the structure of small vertex-transitive graphs of given degree and girth adds to our understanding of the general Cage Problem and may even produce graphs that could possibly be altered to become cages (by giving up some of their symmetry properties). In our talk, we will discuss connections between general and vertex-transitive graphs of given degree and girth and the way progress in understanding either of these two classes may lead to progress in the other.

A {\em bipartite biregular} $(m,n;g)$-graph $\Gamma$ is a bipartite graph of even girth $g$ having the degree set $\{m,n\}$ and satisfying the additional property that the vertices in the same partite set have the same degree. The $(m,n;g)$-{\em bipartite biregular cages}, was introduced in 2019 by Filipovski, Ramos-Rivera, and Jajcay, they are bipartite biregular $(m,n;g)$-graphs of minimum order. The authors calculate lower bounds on the orders of bipartite biregular $(m,n;g)$-graphs, and call the graphs that attain these bounds {\em bipartite biregular Moore cages}. We improve the lower bounds obtained in the above paper. Furthermore, in parallel with the well-known classical results relating the existence of $k$-regular Moore graphs of even girths $g = 6,8 $ and $12$ to the existence of projective planes, generalized quadrangles, and generalized hexagons, we prove that the existence of an $S(2,k,v)$-Steiner system yields the existence of a bipartite biregular $(k,\frac{v-1}{k-1};6)$-cage, and, vice versa, the existence of a bipartite biregular $(k,n;6)$-cage whose order is equal to one of our lower bounds yields the existence of an $S(2,k,1+n(k-1))$-Steiner system. Moreover, in the special case of Steiner triple systems, we completely solve the problem of determining the orders of $(3,n;6)$-bipartite biregular cages for all integers $n\geq 4$. Considering girths higher than $6$, we relate the existence of generalized polygons (quadrangles, hexagons and octagons) to the existence of $(n+1,n^2+1;8)$-, $(n^2+1,n^3+1;8)$-, $(n,n+2;8)$-, $(n+1,n^3+1;12)$- and $(n+1,n^2+1;16)$-bipartite biregular cages, respectively. Using this connection, we also derive improved upper bounds for the orders of other classes of bipartite biregular cages of girths $8$, $12$, and $14$.

Two new classes of graph regularities have been introduced recently. Let $\Gamma$ denote a simple, connected, finite graph. For an edge e of $\Gamma$ let $n(e)$ denote the number of girth cycles containing $e$. For a vertex $v$ of $\Gamma$ let $\{e_1, e_2, \ldots , e_k\}$ be the set of edges incident to $v$ ordered such that $n(e_1) \le n(e_2) \le \ldots\le n(e_k)$. Then $ (n(e_1), n(e_2),\ldots, n(e_k))$ is called the signature of $v$. The graph $\Gamma$ is said to be girth-(bi)regular if (it is bipartite, and) all of its vertices (belonging to the same bipartition) have the same signature. We show that girth-(bi)regular graphs are related to (biregular) cages, finite projective and affine spaces and generalized polygons. We also provide a short, concise introduction to these geometric objects.

The \textit{harmonious chromatic number} of a graph $G$ is the minimum number of colors that can be assigned to the vertices of $G$ in a proper way such that any two distinct edges have different color pairs. Therefore, if $G$ has order $v$ and diameter at most two, then $h(G)=v$. Therefore, if $G$ is the Levi graph of a linear space $\mathcal{S}$ of $n$ points, then $h(G)\geq n$, since every two points in $\mathcal{S}$ determine a line. In [1] is proved that: 1) If $G$ is the Levi graph of the finite projective plane of odd order $q$, then \[q^2+q+ 1\leq h(G) \leq q^2+q+ 2;\] 2) If $G$ is the Levi graph of the complete graph $K_n$, then \[\frac{3}{2}n\leq h(G) \leq \frac{5}{3}n +\theta(1).\] A possible problem is to estimate the harmonious chromatic number of the $(q+1,8)$-cages (the Levi graphs of generalized quadrangles).} References [1] Araujo-Pardo, G., Montellano-Ballesteros, J. J., Olsen, M., and Rubio-Montiel, C. \textit{On the harmonious chromatic number of graphs}. arXiv preprint arXiv:2206.04822, 2022.

Geometric properties can be used to determine chromatic classes of coloring and chromatic classes can determine geometric properties. Packing colorings and $L(h, k)$ colorings are somehow related. The packing chromatic number, $χ_ρ(G)$, of a graph $G$ is the minimum number of colors (positive integer) of a vertex coloring of $G$ such that vertices of color $i$ are at distance at least $i + 1$. The $L(h, k)$ chromatic number, $λ_{h,k}(G)$, of a graph $G$ is the minimum number of colors (non-negative integers) of a vertex coloring of $G$ such that the colors of adjacent vertices must differ in at least $h$ and the colors of vertices of distance $2$ must differ at least $k$. In [1] it was proved that: • Let $q$ be an odd prime power. If $G$ is the Levi graph of a $Q(4, q)$, then $(q^2 + 1)(q − 1) + 3 ≤ χ_ρ(G) ≤ (q^2 + 1)(q − 1) + 4.$ • A $Q(4, q)$ contains two disjoint ovoids or two disjoint spreads if and only if $χ_ρ(G) = (q^2 + 1)(q − 1) + 3$, where G is its Levi graph. In [2] it was proved that: • The points of a $Q(4, q)$ have a partition into a daisy structure and the lines of $Q(4, q)$ have a partition into a sunflower structure. • If $G$ is the Levi graph of a $Q(4, q)$ and $q ≥ 5$ is a prime number then, $(2q + 2)k ≤ λ{h,k}(G) ≤ (q + 1)2k/2 + h.$ A possible problem is to extend the results for Levy graphs of $Q(4, q)$ to Levi graphs of generalized quadrangles which are not $Q(4, q)$, another possible problem es improve the bounds for the packing chromatic number of $(q + 1, 12)$-cages or improve the bounds of $L(h, k)$ chromatic number of Levi graphs of $Q(4, q)$. References [1] J. Fresán-Figueroa, D. González-Moreno, M. Olsen, On the packing chromatic number of Moore graphs, Discrete App. Math. 289 (2021) 185–193. [2] J. Fresán-Figueroa, D. González-Moreno, M. Olsen, Special structures in $Q(4, q)$, projective planes and its application in $L(h, k)$ colorings of their Moore Graphs, Discrete App. Math. 331 (2023) 31–37.

Mixed graphs can be viewed as generalisations of both undirected graphs and digraphs. The problems of the largest (totally regular) mixed graph of given degree and diameter and the smallest such graph of given degree and girth (or geodecity) share some features in common with those for undirected and directed graphs. However, the mixed graph problems have certain unique aspects. We will outline some results from the last few years, and note some open problems and possible lines of attack.

Some problems on cages and degree diameter graphs are surveyed. The focus is on problems where a computational approach to the problem has fallen short, and for which a little non-computer based analysis might be enough to make the computations feasible.

Moore graphs are extremal graphs that appear as solutions of a combinatorial problem known as the degree/diameter problem. This problem is key to the design of topologies for interconnection networks and other questions related to data structures and cryptographic protocols. Besides, the relationship between vertices or nodes in communication networks can be undirected or directed depending on whether the communication between nodes is two-way or only one-way. Mixed graphs arise in this case and it is therefore natural to consider network topologies based on mixed graphs, and investigate the corresponding degree/diameter problem and their solutions (mixed Moore graphs). In this talk we present mixed radial Moore graphs as an approximation of mixed Moore graphs and we describe how to measure they closeness to the properties that a mixed Moore graph should have. References [1] C. Capdevila, J. Conde, G. Exoo, J. Gimbert, N. Lopez, Ranking measures for radially Moore graphs, Networks, 56(4): (2010) 255{262. [2] C. Dalfo, M. A. Fiol, and N. Lopez, Sequence mixed graphs, Discrete Applied Math. 219 (2017) 110{116. [3] C. Dalfo, M. A. Fiol, and N. Lopez, An improved upper bound for the order of mixed graphs, Discrete Math. 341 (2018), no. 10, 2872{2877. [4] G. Exoo, J. Gimbert, N. Lopez, J. Gomez, Radial moore graphs of radius three, Discrete Applied Math., 160(10), (2012), 1507{1512. [5] M. Miller and J. Siran, Moore graphs and beyond: A survey of the degree/diameter problem, Electron. J. Combin. 20(2) (2013) #DS14v2. [6] M. H. Nguyen, M. Miller, and J. Gimbert, On mixed Moore graphs, Discrete Math. 307 (2007) 964{970.

For integers $r \ge 2$ and $g \ge 3,$ an $(r,g)$-\emph{graph} is and $r$-regular graph with girth $g$, and an $(r,g)$-\emph{cage} is an $(r,g)$-graph of minimum order. It is conjectured that all $(r,g)$-cages with even $g$ are bipartite, that is, have chromatic number $2$. Here we introduce the idea of an $(r,g, \chi)$-\emph{graph}, an $r$-regular graph with girth $g$ and chromatic number $\chi$. We investigate the existence of such graphs and study in detail the $(r,3,3)$-graphs of minimum order. We also consider $(r,g, \chi)$-graphs for which there is a $\chi$-coloring where the color classes differ by at most $1$.

I will try to give an overview of the main constructions for classic designs and graph decompositions that my collaborators and I obtained over the years with the so-called {\it method of differences} and its many variants.

Available rooms for group work: Keguli Room (Main Lecture room) Vermillion Room (Buffet room) 3rd floor suite (Follow stairs outside of the bistro entrance to top floor) Cabin (Across the parking lot - check with organizer for Cabin number)

Available rooms for group work: Keguli Room (Main Lecture room) Vermillion Room (Buffet room) 3rd floor suite (Follow stairs outside of the bistro entrance to top floor) Cabin (Across the parking lot - check with organizer for Cabin number)

The $k$-token graph $F_k(G)$ of a graph $G$ is the graph whose vertices are the $k$-subsets of vertices from $G$, two of which being adjacent whenever their symmetric difference is a pair of adjacent vertices in $G$. In this talk, through lift graphs and voltage assignments, we first show the spectrum of a $k$-token graph of a cycle $C_n$ for some $n$. Since this technique does not give the results for all possible $n$, we introduce a new method that we called over-lifts. This method allows us to present the spectra of any $k$-token graph of any cycle $C_n$.

The $k$-token graph $F_k(G)$ of a graph $G$ is the graph whose vertices are the $k$-subsets of vertices from $G$, two of which being adjacent whenever their symmetric difference is a pair of adjacent vertices in $G$. In this talk, through lift graphs and voltage assignments, we first show the spectrum of a $k$-token graph of a cycle $C_n$ for some $n$. Since this technique does not give the results for all possible $n$, we introduce a new method that we called over-lifts. This method allows us to present the spectra of any $k$-token graph of any cycle $C_n$.

The $k$-token graph $F_k(G)$ of a graph $G$ is the graph whose vertices are the $k$-subsets of vertices from $G$, two of which being adjacent whenever their symmetric difference is a pair of adjacent vertices in $G$. In this talk, through lift graphs and voltage assignments, we first show the spectrum of a $k$-token graph of a cycle $C_n$ for some $n$. Since this technique does not give the results for all possible $n$, we introduce a new method that we called over-lifts. This method allows us to present the spectra of any $k$-token graph of any cycle $C_n$.

An edge-girth-regular graph $egr(v,k,g,\lambda)$, is a $k$-regular graph of order $v$, girth $g$ and with the property that each of its edges is contained in exactly $\lambda$ distinct $g$-cycles. An $egr(v,k,g,\lambda)$ is called extremal for the triple $(k,g,\lambda)$ if $v$ is the smallest order of any $egr(v,k,g,\lambda)$. In this talk, I will show two families of edge-girth-regular graphs. The first one is a family of extremal $egr(2q^2,q,6,(q-1)^2(q-2))$ for any prime power $q\geq 3$. The second one is a family of $egr(q(q^2+1),q,5,\lambda)$ for $\lambda\geq q-1$ and $q\geq 8$ an odd power of $2$. In particular, if $q=8$ we have that $\lambda=q-1$.

Available rooms for group work: Keguli Room (Main Lecture room) Vermillion Room (Buffet room) 3rd floor suite (Follow stairs outside of the bistro entrance to top floor) Cabin (Across the parking lot - check with organizer for Cabin number)

Available rooms for group work: Keguli Room (Main Lecture room) Vermillion Room (Buffet room) 3rd floor suite (Follow stairs outside of the bistro entrance to top floor) Cabin (Across the parking lot - check with organizer for Cabin number)