A CLASSIFICATION OF Q Q -POLYNOMIAL DISTANCE-REGULAR GRAPHS WITH GIRTH 6 6

Štefko Miklavič · 2025

Read A CLASSIFICATION OF Q Q -POLYNOMIAL DISTANCE-REGULAR GRAPHS WITH GIRTH 6 6 by Štefko Miklavič (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-12820.txt.

Introduction

Štefko Miklavič sorts a special family of highly regular graphs whose shortest loop has length six, in a paper from two thousand twenty-five. The graphs are distance-regular and carry a Q-polynomial structure, terms the author uses in their strict math sense. An older result capped the shortest loop at six for this family.

Miklavič shows the cap is reached in just two cases. One is the Odd graph built on a set sized by the graph span, and the other is a generalized hexagon of a stated order. No other graph in the family attains the bound. Readers in algebraic graph theory get a clean end to a classification question.

Catalog record

CREATORŠtefko Miklavič
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE21 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-12820

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A CLASSIFICATION OF Q Q -POLYNOMIAL DISTANCE-REGULAR GRAPHS WITH GIRTH 6 6 Štefko Miklavič Abstract Let Γ \Gamma denote a Q Q -polynomial distance-regular graph with diameter D D and valency k ≥ 3 k\geq 3 . In [Homotopy in Q Q -polynomial distance-regular graphs, Discrete Math., 223 (2000), 189–206], H. Lewis showed that the girth of Γ \Gamma is at most 6 6 . In this paper we classify graphs that attain this upper bound. We show that Γ \Gamma has girth 6 6 if and only if it is either isomorphic to the Odd graph on a set of cardinality 2 ​ D + 1 2D+1 , or to a generalized hexagon of order ( 1 , k − 1 ) (1,k-1) . 1 Introduction Let \Gamma denote a Q -polynomial distance-regular graph with diameter D , valency k\geq 3 , and intersection numbers a_{i},b_{i},c_{i} (see Sections 2 and 3 for formal definitions). In [ 8 , Corollary 30] , H. Lewis showed that the girth of \Gamma is at most 6 . Therefore, the problem of classification of Q -polynomial distance-regular graphs that attain this upper bound arises naturally. In the present paper we show that \Gamma has girth 6 if and only if it is either isomorphic to the Odd graph on a set of cardinality 2D+1 , or to a generalized hexagon of order (1,k-1) . Our strategy for proving the above result is as follows. If \Gamma has girth 6 , then a_{1}=a_{2}=0 and c_{2}=1 . It follows from [ 9 , Theorem 6.3] that in this case \Gamma is either bipartite or almost bipartite. We treat these two cases separately. We now briefly summarize what was done so far for each of the above two cases. The classification of almost bipartite Q -polynomial distance-regular graphs with D\geq 4 is given in [ 7 , Theorem 1.1] . It transpires that if \Gamma is almost bipartite with D\geq 4 and girth 6 , then it is the Odd graph on a set of cardinality 2D+1 . Therefore, it remains to consider the case D=3 . We do this in Section 4 . Assume next that \Gamma is bipartite with diameter D\geq 3 and valency k\geq 3 . In [ 5 , Theorem 1.1] , Caughman showed that if D\geq 12 , then \Gamma is the D -dimensional hypercube, or the folded 2D -dimensional hypercube, or the intersection numbers of \Gamma satisfy c_{i}=(q^{i}-1)/(q-1)\;(1\leq i\leq D) , where q\geq 2 is an integer. In [ 11 ] , this result was extended to the case D\geq 9 . Therefore, if D\geq 9 , then c_{2}\geq 2 (and so \Gamma has girth 4 ). In [ 10 , Theorem 6.1] we proved that if D=4 , then again c_{2}\geq 2 , hence also in this case girth equals 4 . If D=3 , then \Gamma is clearly isomorphic to a generalized hexagon of order (1,k-1) . In the present paper we focus on the case 5\leq D\leq 8 . It turns out that the case D=5 is the most difficult one. Therefore, we treate the cases D\geq 6 and D=5 in separate sections. In Section 5 , we show that if D\geq 6 , then c_{2}\geq 2 , and so \Gamma has girth 4. We show the same result for the case D=5 in Section 6 . 2 Preliminaries In this section, we review some definitions and basic concepts regarding distance-regular graphs. See the book of Brouwer, Cohen and Neumaier [ 3 ] for more background information. Throughout this paper, \Gamma=(X,R) will denote a finite, undirected, connected graph, without loops or multiple edges, with vertex set X , edge set R , path length distance function \partial , and diameter D:=max\{\partial(x,y)|x,y\in X\} . For a vertex x\in X define \Gamma_{i}(x) to be the set of vertices at distance i from x . We abbreviate \Gamma(x):=\Gamma_{1}(x) . Let k denote a non-negative integer. Then \Gamma is said to be regular with valency k whenever |\Gamma(x)|=k for all x\in X . The graph \Gamma is said to be distance-regular whenever for all integers h,i,j\;(0\leq h,i,j\leq D) , and all x,y\in X with \partial(x,y)=h , the number p^{h}_{ij}:=|\Gamma_{i}(x)\cap\Gamma_{j}(y)| is independent of x,y . The constants p^{h}_{ij} are known as the intersection numbers of \Gamma . For convenience, set c_{i}:=p^{i}_{1,i-1} for 1\leq i\leq D , a_{i}:=p^{i}_{1i} for 0\leq i\leq D , b_{i}:=p^{i}_{1,i+1} for 0\leq i\leq D-1 , k_{i}:=p^{0}_{ii} for 0\leq i\leq D , and c_{0}=b_{D}=0 . We observe a_{0}=0 and c_{1}=1 . Moreover, \Gamma is regular with valency k=b_{0}=k_{1} , and c_{i}+a_{i}+b_{i}=k for 0\leq i\leq D . It is well-known that k_{i}=\frac{b_{0}b_{1}\cdots b_{i-1}}{c_{1}c_{2}\cdots c_{i}} (1) for 0\leq i\leq D . Observe that \Gamma is bipartite if and only if a_{i}=0 for 0\leq i\leq D . In this case b_{i}+c_{i}=k for 0\leq i\leq D . We say that \Gamma is almost bipartite , whenever a_{i}=0 for 0\leq i\leq D-1 and a_{D}\neq 0 . The following families of distance-regular graphs will appear in this paper: hypercubes (see [ 3 , Section 9.2] ), folded hypercubes (see [ 3 , Subsection 9.2 D] ), Odd graphs (see [ 3 , Subsection 9.1 D] ), and generalized hexagons (see [ 3 , Section 6.5] ). Observe that if D\leq 2 , then the girth of \Gamma is at most 5 . Therefore, from now on we assume \Gamma is distance-regular with diameter D\geq 3 and valency k\geq 3 .v Throughout the paper we will be extensively using the following result without explicitly referring to it. Lemma 2.1 Let \Gamma denote a distance-regular graph with diameter D\geq 3 and valency k\geq 3 . Then the following (i), (ii) hold. (i) The girth of \Gamma is at least 6 if and only if a_{1}=a_{2}=0 and c_{2}=1 . (ii) If \Gamma is isomorphic to the D -cube, or to the folded 2D -cube, or to the folded (2D+1) -cube, then a_{1}=0 and c_{2}=2 . In particular, the girth of \Gamma is equal to 4 . We recall the Bose-Mesner algebra of \Gamma . Let \mat_{X}(\mathbb{C}) denote the \mathbb{C} -algebra consisting of the matrices over \mathbb{C} which have rows and columns indexed by X . For 0\leq i\leq D let A_{i} denote the matrix in \mat_{X}(\mathbb{C}) with x,y entry \left(A_{i}\right)_{xy}=\begin{cases}\hskip 5.69046pt1\hskip 14.22636pt\text{if}&\partial(x,y)=i,\\ \hskip 5.69046pt0\hskip 14.22636pt\text{if}&\partial(x,y)\neq i\end{cases}\qquad(x,y\in X). We call A_{i} the i -th distance matrix of \Gamma . We abbreviate A:=A_{1} and call A the adjacency matrix of \Gamma . The matrices A_{0},A_{1},\ldots,A_{D} form a basis for a commutative semi-simple \mathbb{C} -algebra M , known as the Bose-Mesner algebra , see for example [ 3 , p. 44] . By [ 3 , Theorem 2.6.1] the algebra M has a second basis E_{0},E_{1},\ldots,E_{D} , such that E_{i}E_{j}=\delta_{ij}E_{i}\;(0\leq i,j\leq D) , E_{0}+E_{1}+\cdots+E_{D}=I , and E_{0}=|X|^{-1}J , where I and J denote the identity and the all 1’s matrix of \mat_{X}(\mathbb{C}) , respectively. The E_{0},E_{1},\ldots,E_{D} are known as the primitive idempotents of \Gamma , and we refer to E_{0} as the trivial idempotent of \Gamma . For 0\leq i\leq D define a real number \theta_{i} by A=\sum_{i=0}^{D}\theta_{i}E_{i} . Then AE_{i}=E_{i}A=\theta_{i}E_{i} for 0\leq i\leq D . The scalars \theta_{0},\theta_{1},\ldots,\theta_{D} are distinct since A generates M [ 2 , p. 197] . The

Read the complete text