On Subgraphs in Distance-Regular Graphs
J.H. Koolen
DOI: 10.1023/A:1022442717593
Abstract
Terwilliger [15] has given the diameter bound d 
(s - 1)( k - 1) + 1 for distance-regular graphs with girth 2 s 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.
(s - 1)( k - 1) + 1 for distance-regular graphs with girth 2 s 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.Pages: 353–362
Keywords: distance-regular graph; hypercubes; doubled odd graph; subgraph; uniformly geodetic graph
Full Text: PDF
References
1. E. Bannai and T. Ito, "On finite Moore graphs," ]. Fac. Sci. Univ. Tokyo, Sect IA 20 (1973) 191-208.
2. A.E. Brouwer, "On the uniqueness of a certain thin near octagon (or partial 2-geometry, or parallelism) derived from the binary Golay code," IEEE Trans. Inform. Theory JT-29 (1983) 370-371.
3. A.E. Brouwer, "Uniqueness and non-existence of some graphs related to M22," Graphs Combin. 2 (1986) 21-29. KOOLEN
4. A.E. Brouwer, A.M. Cohen, and A. Neumaier, Distance-regular graphs, Ergebnisse der Mathematik 3.18, Springer, Heidelberg, 1989.
5. A.E. Brouwer and H.A. Wilbrink, "The structure of near polygon with quads," Geom. Dedicata 14 (1983) 145-176.
6. J. Chima, "Near n-gons with thin lines," Ph.D. Dissertation, Kansas State University (1982).
7. R.M. Damerell, "On Moore graphs," Proc. Cambridge Philos. Soc. 74 (1973) 227-236.
8. A.A. Ivanov, "On 2-transitive graphs of girth 5," European J. Combin. 8 (1987) 393-420.
9. J.H. Koolen, "On uniformly geodetic graphs," preprint (1990), submitted to Graphs Combin.
10. J.H. Koolen, "A new condition for distance-regular graphs," European J. Combin. 13 (1992) 63-64.
11. H.M. Mulder, "The interval function of a graph," Ph.D. Thesis, Math. Centre Tract 132, Mathematisch Centrum, Amsterdam, 1980.
12. H.M. Mulder, "Interval-regular graphs," Discrete Math. 41 (1982) 253-269.
13. O.Ore, Theory of graphs, Amer. Math. Soc., Providence, R.I. (1962).
14. D.K. Ray-Chaudhuri and A.P. Sprague, "Characterization of projective incidence structures," Geom. Dedicata 5 (1976) 361-376.
15. P. Terwilliger, "Distance-regular graphs and (s, c, a, k)-graphs," J. Combin. Theory Ser. B 34 (1983) 151-164.
16. P. Terwilliger, "Root systems and the Johnson and Hamming graphs," European J. Combin. 8 (1987) 73-102.
17. P.M. Weichsel, "Distance regular subgraphs of a cube," preprint, to appear in Discrete Math.
2. A.E. Brouwer, "On the uniqueness of a certain thin near octagon (or partial 2-geometry, or parallelism) derived from the binary Golay code," IEEE Trans. Inform. Theory JT-29 (1983) 370-371.
3. A.E. Brouwer, "Uniqueness and non-existence of some graphs related to M22," Graphs Combin. 2 (1986) 21-29. KOOLEN
4. A.E. Brouwer, A.M. Cohen, and A. Neumaier, Distance-regular graphs, Ergebnisse der Mathematik 3.18, Springer, Heidelberg, 1989.
5. A.E. Brouwer and H.A. Wilbrink, "The structure of near polygon with quads," Geom. Dedicata 14 (1983) 145-176.
6. J. Chima, "Near n-gons with thin lines," Ph.D. Dissertation, Kansas State University (1982).
7. R.M. Damerell, "On Moore graphs," Proc. Cambridge Philos. Soc. 74 (1973) 227-236.
8. A.A. Ivanov, "On 2-transitive graphs of girth 5," European J. Combin. 8 (1987) 393-420.
9. J.H. Koolen, "On uniformly geodetic graphs," preprint (1990), submitted to Graphs Combin.
10. J.H. Koolen, "A new condition for distance-regular graphs," European J. Combin. 13 (1992) 63-64.
11. H.M. Mulder, "The interval function of a graph," Ph.D. Thesis, Math. Centre Tract 132, Mathematisch Centrum, Amsterdam, 1980.
12. H.M. Mulder, "Interval-regular graphs," Discrete Math. 41 (1982) 253-269.
13. O.Ore, Theory of graphs, Amer. Math. Soc., Providence, R.I. (1962).
14. D.K. Ray-Chaudhuri and A.P. Sprague, "Characterization of projective incidence structures," Geom. Dedicata 5 (1976) 361-376.
15. P. Terwilliger, "Distance-regular graphs and (s, c, a, k)-graphs," J. Combin. Theory Ser. B 34 (1983) 151-164.
16. P. Terwilliger, "Root systems and the Johnson and Hamming graphs," European J. Combin. 8 (1987) 73-102.
17. P.M. Weichsel, "Distance regular subgraphs of a cube," preprint, to appear in Discrete Math.