On Subgraphs in Distance-Regular Graphs |
| |
Authors: | J.H. Koolen |
| |
Affiliation: | (1) Dept. of Math. and Comp. Sci., Eindhoven Univ. of Techn., P.O. Box 513, 5600MB Eindhoven, The Netherlands |
| |
Abstract: | Terwilliger [15] has given the diameter bound d (s – 1)(k – 1) + 1 for distance-regular graphs with girth 2s and valency k. We show that the only distance-regular graphs with even girth which reach this bound are the hypercubes and the doubled Odd graphs. Also we improve this bound for bipartite distance-regular graphs. Weichsel [17] conjectures that the only distance-regular subgraphs of a hypercube are the even polygons, the hypercubes and the doubled Odd graphs and proves this in the case of girth 4. We show that the only distance-regular subgraphs of a hypercube with girth 6 are the doubled Odd graphs. If the girth is equal to 8, then its valency is at most 12. |
| |
Keywords: | distance-regular graph hypercubes doubled odd graph subgraph uniformly geodetic graph |
本文献已被 SpringerLink 等数据库收录! |
|