A spectral version of the Moore problem for bipartite regular graphs

Cioabă, Sebastian M.; Koolen, Jack H.; Nozaki, Hiroshi

doi:10.5802/alco.71

Cioabă, Sebastian M.¹ ; Koolen, Jack H.² ; Nozaki, Hiroshi ³

¹ University of Delaware Department of Mathematical Sciences Ewing Hall Newark, DE 19716-2553, USA
² School of Mathematical Sciences University of Science and Technology of China Wen-Tsun Wu Key Laboratory of the Chinese Academy of Sciences Hefei, Anhui, China
³ Aichi University of Education 1 Hirosawa, Igaya-cho, Kariya Aichi 448-8542, Japan

Algebraic Combinatorics, Tome 2 (2019) no. 6, pp. 1219-1238

Voir la notice de l'article provenant de la source Numdam

Résumé

Let $b (k, θ)$ be the maximum order of a connected bipartite $k$ -regular graph whose second largest eigenvalue is at most $θ$ . In this paper, we obtain a general upper bound for $b (k, θ)$ for any $0 \leq θ < 2 \sqrt{k - 1}$ . Our bound gives the exact value of $b (k, θ)$ whenever there exists a bipartite distance-regular graph of degree $k$ , second largest eigenvalue $θ$ , diameter $d$ and girth $g$ such that $g \geq 2 d - 2$ . For certain values of $d$ , there are infinitely many such graphs of various valencies $k$ . However, for $d = 11$ or $d \geq 15$ , we prove that there are no bipartite distance-regular graphs with $g \geq 2 d - 2$ .

Reçu le : 2018-05-02
Révisé le : 2019-03-04
Accepté le : 2019-03-04
Publié le : 2019-12-04

MR Zbl

DOI : 10.5802/alco.71

Classification : 05B25, 05C35, 05C50, 05E30, 42C05, 94B65
Keywords: second eigenvalue, bipartite regular graph, bipartite distance-regular graph, expander, linear programming bound.

Affiliations des auteurs :

Cioabă, Sebastian M. ¹ ; Koolen, Jack H. ² ; Nozaki, Hiroshi ³

¹ University of Delaware Department of Mathematical Sciences Ewing Hall Newark, DE 19716-2553, USA
² School of Mathematical Sciences University of Science and Technology of China Wen-Tsun Wu Key Laboratory of the Chinese Academy of Sciences Hefei, Anhui, China
³ Aichi University of Education 1 Hirosawa, Igaya-cho, Kariya Aichi 448-8542, Japan

Licence :

CC-BY 4.0

Droits d'auteur : Les auteurs conservent leurs droits

@article{ALCO_2019__2_6_1219_0,
     author = {Cioab\u{a}, Sebastian M. and Koolen, Jack H. and Nozaki, Hiroshi},
     title = {A spectral version of the {Moore} problem for bipartite regular graphs},
     journal = {Algebraic Combinatorics},
     pages = {1219--1238},
     publisher = {MathOA foundation},
     volume = {2},
     number = {6},
     year = {2019},
     doi = {10.5802/alco.71},
     mrnumber = {4049844},
     zbl = {1428.05187},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.5802/alco.71/}
}

TY  - JOUR
AU  - Cioabă, Sebastian M.
AU  - Koolen, Jack H.
AU  - Nozaki, Hiroshi
TI  - A spectral version of the Moore problem for bipartite regular graphs
JO  - Algebraic Combinatorics
PY  - 2019
SP  - 1219
EP  - 1238
VL  - 2
IS  - 6
PB  - MathOA foundation
UR  - http://geodesic.mathdoc.fr/articles/10.5802/alco.71/
DO  - 10.5802/alco.71
LA  - en
ID  - ALCO_2019__2_6_1219_0
ER  -

%0 Journal Article
%A Cioabă, Sebastian M.
%A Koolen, Jack H.
%A Nozaki, Hiroshi
%T A spectral version of the Moore problem for bipartite regular graphs
%J Algebraic Combinatorics
%D 2019
%P 1219-1238
%V 2
%N 6
%I MathOA foundation
%U http://geodesic.mathdoc.fr/articles/10.5802/alco.71/
%R 10.5802/alco.71
%G en
%F ALCO_2019__2_6_1219_0

Cioabă, Sebastian M.; Koolen, Jack H.; Nozaki, Hiroshi. A spectral version of the Moore problem for bipartite regular graphs. Algebraic Combinatorics, Tome 2 (2019) no. 6, pp. 1219-1238. doi: 10.5802/alco.71

Cité par Sources :

Parcourir par

Geodesic

Parcourir par