On bipartite cages of excess 4

Slobodan Filipovski¹

¹University of Primorska

The electronic journal of combinatorics, Tome 24 (2017) no. 1

Résumé

The Moore bound $M(k,g)$ is a lower bound on the order of $k$-regular graphs of girth $g$ (denoted $(k,g)$-graphs). The excess $e$ of a $(k,g)$-graph of order $n$ is the difference $ n-M(k,g) $. In this paper we consider the existence of $(k,g)$-bipartite graphs of excess $4$ by studying spectral properties of their adjacency matrices. For a given graph $G$ and for the integers $i$ with $0\leq i\leq diam(G)$, the $i$-distance matrix $A_i$ of $G$ is an $n\times n$ matrix such that the entry in position $(u,v)$ is $1$ if the distance between the vertices $u$ and $v$ is $i$, and zero otherwise. We prove that the $(k,g)$-bipartite graphs of excess $4$ satisfy the equation $kJ=(A+kI)(H_{d-1}(A)+E)$, where $A=A_{1}$ denotes the adjacency matrix of the graph in question, $J$ the $n \times n$ all-ones matrix, $E=A_{d+1}$ the adjacency matrix of a union of vertex-disjoint cycles, and $H_{d-1}(x)$ is the Dickson polynomial of the second kind with parameter $k-1$ and degree $d-1$. We observe that the eigenvalues other than $\pm k$ of these graphs are roots of the polynomials $H_{d-1}(x)+\lambda$, where $\lambda$ is an eigenvalue of $E$. Based on the irreducibility of $H_{d-1}(x)\pm2$, we give necessary conditions for the existence of these graphs. If $E$ is the adjacency matrix of a cycle of order $n$, we call the corresponding graphs graphs with cyclic excess; if $E$ is the adjacency matrix of a disjoint union of two cycles, we call the corresponding graphs graphs with bicyclic excess. In this paper we prove the non-existence of $(k,g)$-graphs with cyclic excess $4$ if $k\geq6$ and $k \equiv1 \!\! \pmod {3}$, $g=8, 12, 16$ or $k \equiv2 \!\! \pmod {3}$, $g=8;$ and the non-existence of $(k,g)$-graphs with bicyclic excess $4$ if $k\geq7$ is an odd number and $g=2d$ such that $d\geq4$ is even.

Détail

DOI : 10.37236/6693

Classification : 05C38, 05C50
Mots-clés : cage problem, bipartite graphs, cyclic excess, bicyclic excess