Restrictions on classical distance-regular graphs

被引:7
作者
Jurisic, Aleksandar [1 ,2 ]
Vidali, Janos [3 ]
机构
[1] Univ Ljubljana, Fac Comp & Informat Sci, Ljubljana 1000, Slovenia
[2] Univ Ljubljana, IMFM, Ljubljana 1000, Slovenia
[3] Univ Ljubljana, Fac Math & Phys, Ljubljana 1000, Slovenia
关键词
Distance-regular graphs; Classical parameters; Formally self-dual; Tight graphs; Locally strongly regular; ASSOCIATION SCHEMES; FORMS;
D O I
10.1007/s10801-017-0765-3
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
Let be a distance-regular graph with diameter . It is said to have classical parameters when its intersection array satisfies where . Apart from the well-known families, there are many sets of classical parameters for which the existence of a corresponding graph is still open. It turns out that in most such cases we have either or . For these two cases, we derive bounds on the parameter , which give us complete classifications when . Distance-regular graphs with classical parameters are antipodal iff and . If we drop the condition , it turns out that one obtains either bipartite or tight graphs. For the latter graphs, we find closed formulas for the parameters of the CAB partitions and the distance partition corresponding to an edge. Finally, we find a two-parameter family of feasible intersection arrays for tight distance-regular graphs with classical parameters (primitive iff ) and apply our results to show that it is realized only by d-cubes (b = 1).
引用
收藏
页码:571 / 588
页数:18
相关论文
共 26 条
[1]  
[Anonymous], 1989, RESULTS MATH RELATED
[3]  
Brouwer A. E., 2011, PARAMETERS DISTANCE
[4]   A distance regular graph with intersection array (21,16,8; 1,4,14) does not exist [J].
Coolsaet, K .
EUROPEAN JOURNAL OF COMBINATORICS, 2005, 26 (05) :709-716
[5]   Using equality in the Krein conditions to prove nonexistence of certain distance-regular graphs [J].
Coolsaet, Kris ;
Jurisic, Aleksandar .
JOURNAL OF COMBINATORIAL THEORY SERIES A, 2008, 115 (06) :1086-1095
[6]   On Q-polynomial regular near 2d-gons [J].
De Bruyn, Bart ;
Vanhove, Frederic .
COMBINATORICA, 2015, 35 (02) :181-208
[7]   CHARACTERIZATION OF H(N,Q) BY THE PARAMETERS [J].
EGAWA, Y .
JOURNAL OF COMBINATORIAL THEORY SERIES A, 1981, 31 (02) :108-125
[8]  
Godsil C. D, 1993, ALGEBRAIC COMBINATOR, DOI [10.1201/9781315137131, DOI 10.1201/9781315137131]
[9]  
Huang YP, 2015, ELECTRON J COMB, V22
[10]   CHARACTERIZATION OF THE ASSOCIATION SCHEMES OF HERMITIAN-FORMS OVER GF2[2] [J].
IVANOV, AA ;
SHPECTOROV, SV .
GEOMETRIAE DEDICATA, 1989, 30 (01) :23-33