Towards a classification of $1$-homogeneous distance-regular graphs with positive intersection number $a_1$

Koolen, Jack H.; Abdullah, Mamoon; Gebremichel, Brhane; Lee, Jae-Ho

doi:10.5802/alco.454

Koolen, Jack H.^1,²; Abdullah, Mamoon ¹; Gebremichel, Brhane ³; Lee, Jae-Ho ⁴

¹ School of Mathematical Sciences, University of Science and Technology of China, Hefei, Anhui, 230026 (PR China)
² CAS Wu Wen-Tsun Key Laboratory of Mathematics, University of Science and Technology of China, Hefei, Anhui, 230026 (PR China)
³ Department of Mathematics, Adigrat University, Adigrat, Tigray, 7040 (Ethiopia)
⁴ Department of Mathematics and Statistics, University of North Florida, Jacksonville, FL 32224 (USA)

Algebraic Combinatorics, Volume 8 (2025) no. 6, pp. 1529-1546

Abstract

Let $\Gamma $ be a graph with diameter at least two. Then $\Gamma $ is said to be $1$-homogeneous (in the sense of Nomura) whenever for every pair of adjacent vertices $x$ and $y$ in $\Gamma $, the distance partition of the vertex set of $\Gamma $ with respect to both $x$ and $y$ is equitable, and the parameters corresponding to equitable partitions are independent of the choice of $x$ and $y$. Assume that $\Gamma $ is $1$-homogeneous distance-regular with intersection number $a_1>0$ and diameter $D\geqslant 5$. Define $b=b_1/(\theta _1+1)$, where $b_1$ is the intersection number and $\theta _1$ is the second largest eigenvalue of $\Gamma $. We show that if intersection number $c_2$ is at least $2$, then $b\geqslant 1$ and one of the following (i)–(vi) holds: (i) $\Gamma $ is a regular near $2D$-gon, (ii) $\Gamma $ is a Johnson graph $J(2D,D)$, (iii) $\Gamma $ is a halved $\ell $-cube with $\ell \in \lbrace 2D,2D+1\rbrace $, (iv) $\Gamma $ is a folded Johnson graph $\bar{J}(4D,2D)$, (v) $\Gamma $ is a folded halved $4D$-cube, (vi) the valency of $\Gamma $ is bounded by a function of $b$. Using this result, we characterize $1$-homogeneous graphs with classical parameters and $a_1>0$, as well as tight distance-regular graphs.

Received: 2025-01-06
Revised: 2025-06-18
Accepted: 2025-09-22
Published online: 2026-01-06

DOI: 10.5802/alco.454

Classification: 05E30, 05C50
Keywords: distance-regular graph, $1$-homogeneous, local graph, classical parameters, tight graph

Author's affiliations:

Koolen, Jack H. ^{1, 2}; Abdullah, Mamoon ¹; Gebremichel, Brhane ³; Lee, Jae-Ho ⁴

¹ School of Mathematical Sciences, University of Science and Technology of China, Hefei, Anhui, 230026 (PR China)
² CAS Wu Wen-Tsun Key Laboratory of Mathematics, University of Science and Technology of China, Hefei, Anhui, 230026 (PR China)
³ Department of Mathematics, Adigrat University, Adigrat, Tigray, 7040 (Ethiopia)
⁴ Department of Mathematics and Statistics, University of North Florida, Jacksonville, FL 32224 (USA)

License:

CC-BY 4.0

Copyrights: The authors retain unrestricted copyrights and publishing rights

@article{ALCO_2025__8_6_1529_0,
     author = {Koolen, Jack H. and Abdullah, Mamoon and Gebremichel, Brhane and Lee, Jae-Ho},
     title = {Towards a classification of $1$-homogeneous distance-regular graphs with positive intersection number $a_1$},
     journal = {Algebraic Combinatorics},
     pages = {1529--1546},
     year = {2025},
     publisher = {The Combinatorics Consortium},
     volume = {8},
     number = {6},
     doi = {10.5802/alco.454},
     language = {en},
     url = {https://alco.centre-mersenne.org/articles/10.5802/alco.454/}
}

TY  - JOUR
AU  - Koolen, Jack H.
AU  - Abdullah, Mamoon
AU  - Gebremichel, Brhane
AU  - Lee, Jae-Ho
TI  - Towards a classification of $1$-homogeneous distance-regular graphs with positive intersection number $a_1$
JO  - Algebraic Combinatorics
PY  - 2025
SP  - 1529
EP  - 1546
VL  - 8
IS  - 6
PB  - The Combinatorics Consortium
UR  - https://alco.centre-mersenne.org/articles/10.5802/alco.454/
DO  - 10.5802/alco.454
LA  - en
ID  - ALCO_2025__8_6_1529_0
ER  -

%0 Journal Article
%A Koolen, Jack H.
%A Abdullah, Mamoon
%A Gebremichel, Brhane
%A Lee, Jae-Ho
%T Towards a classification of $1$-homogeneous distance-regular graphs with positive intersection number $a_1$
%J Algebraic Combinatorics
%D 2025
%P 1529-1546
%V 8
%N 6
%I The Combinatorics Consortium
%U https://alco.centre-mersenne.org/articles/10.5802/alco.454/
%R 10.5802/alco.454
%G en
%F ALCO_2025__8_6_1529_0

Koolen, Jack H.; Abdullah, Mamoon; Gebremichel, Brhane; Lee, Jae-Ho. Towards a classification of $1$-homogeneous distance-regular graphs with positive intersection number $a_1$. Algebraic Combinatorics, Volume 8 (2025) no. 6, pp. 1529-1546. doi: 10.5802/alco.454

References
Cited by

[1] Bang, S.; Dubickas, A.; Koolen, J. H.; Moulton, V. There are only finitely many distance-regular graphs of fixed valency greater than two, Adv. Math., Volume 269 (2015), pp. 1-55 | DOI | MR | Zbl

[2] Brouwer, A. E.; Cohen, A. M.; Neumaier, A. Distance-regular graphs, Ergebnisse der Mathematik und ihrer Grenzgebiete (3), 18, Springer-Verlag, Berlin, 1989, xviii+495 pages | DOI | MR | Zbl

[3] Brouwer, Andries E.; Van Maldeghem, H. Strongly regular graphs, Encyclopedia of Mathematics and its Applications, 182, Cambridge University Press, Cambridge, 2022, xvii+462 pages | DOI | MR | Zbl

[4] Curtin, Brian; Nomura, Kazumasa Homogeneity of a distance-regular graph which supports a spin model, J. Algebraic Combin., Volume 19 (2004) no. 3, pp. 257-272 | DOI | MR | Zbl

[5] Curtin, Brian; Nomura, Kazumasa 1-homogeneous, pseudo-1-homogeneous, and 1-thin distance-regular graphs, J. Combin. Theory Ser. B, Volume 93 (2005) no. 2, pp. 279-302 | DOI | MR | Zbl

[6] Dam, Edwin R. van; Koolen, Jack H.; Tanaka, Hajime Distance-regular graphs, Electron. J. Combin., Volume DS22 (2016), pp. 1-156 | MR | Zbl

[7] Godsil, Chris; Royle, Gordon Algebraic graph theory, Graduate Texts in Mathematics, 207, Springer-Verlag, New York, 2001, xx+439 pages | DOI | MR | Zbl

[8] Jurišić, Aleksandar; Koolen, Jack A local approach to 1-homogeneous graphs, Des. Codes Cryptogr., Volume 21 (2000) no. 1-3, pp. 127-147 | DOI | MR | Zbl

[9] Jurišić, Aleksandar; Koolen, Jack Nonexistence of some antipodal distance-regular graphs of diameter four, European J. Combin., Volume 21 (2000) no. 8, pp. 1039-1046 | DOI | MR | Zbl

[10] Jurišić, Aleksandar; Koolen, Jack Krein parameters and antipodal tight graphs with diameter 3 and 4, Discrete Math., Volume 244 (2002) no. 1-3, pp. 181-202 | DOI | MR | Zbl

[11] Jurišić, Aleksandar; Koolen, Jack 1-homogeneous graphs with cocktail party $μ$ -graphs, J. Algebraic Combin., Volume 18 (2003) no. 2, pp. 79-98 | DOI | MR | Zbl

[12] Jurišić, Aleksandar; Koolen, Jack Distance-regular graphs with complete multipartite $μ$ -graphs and AT4 family, J. Algebraic Combin., Volume 25 (2007) no. 4, pp. 459-471 | DOI | MR | Zbl

[13] Jurišić, Aleksandar; Koolen, Jack Classification of the family $AT 4 (q s, q, q)$ of antipodal tight graphs, J. Combin. Theory Ser. A, Volume 118 (2011) no. 3, pp. 842-852 | DOI | MR | Zbl

[14] Jurišić, Aleksandar; Koolen, Jack; Terwilliger, Paul Tight distance-regular graphs, J. Algebraic Combin., Volume 12 (2000) no. 2, pp. 163-197 | DOI | MR | Zbl

[15] Jurišić, Aleksandar; Munemasa, Akihiro; Tagami, Yuki On graphs with complete multipartite $μ$ -graphs, Discrete Math., Volume 310 (2010) no. 12, pp. 1812-1819 | DOI | MR | Zbl

[16] Jurišić, Aleksandar; Vidali, Janoš Restrictions on classical distance-regular graphs, J. Algebraic Combin., Volume 46 (2017) no. 3-4, pp. 571-588 | DOI | MR | Zbl

[17] Koolen, Jack H.; Lee, Jae-Ho; Li, Shuang-Dong; Li, Yun-Han; Liang, Xiaoye; Tan, Ying-Ying On the (non-)existence of tight distance-regular graphs: a local approach, Electron. J. Combin., Volume 31 (2024) no. 2, Paper no. 2.25, 20 pages | DOI | MR | Zbl

[18] Koolen, Jack H.; Park, Jongyook Distance-regular graphs with $a_{1}$ or $c_{2}$ at least half the valency, J. Combin. Theory Ser. A, Volume 119 (2012) no. 3, pp. 546-555 | DOI | MR | Zbl

[19] Miklavič, Štefko $Q$ -polynomial distance-regular graphs with $a_{1} = 0$ , European J. Combin., Volume 25 (2004) no. 7, pp. 911-920 | DOI | MR | Zbl

[20] Neumaier, A. Strongly regular graphs with smallest eigenvalue $- m$ , Arch. Math. (Basel), Volume 33 (1979/80) no. 4, pp. 392-400 | DOI | MR | Zbl

[21] Nomura, K. Homogeneous graphs and regular near polygons, J. Combin. Theory Ser. B, Volume 60 (1994) no. 1, pp. 63-71 | DOI | MR | Zbl

[22] Tan, Ying-Ying; Koolen, Jack H.; Cao, Meng-Yue; Park, Jongyook Thin $Q$ -polynomial distance-regular graphs have bounded $c_{2}$ , Graphs Combin., Volume 38 (2022) no. 6, Paper no. 175, 18 pages | DOI | MR | Zbl

[23] Terwilliger, Paul Distance-regular graphs with girth $3$ or $4$ . I, J. Combin. Theory Ser. B, Volume 39 (1985) no. 3, pp. 265-281 | DOI | MR | Zbl

Cited by Sources: