Almost 2-Homogeneous Graphs and Completely Regular Quadrangles |
| |
Authors: | Hiroshi Suzuki |
| |
Institution: | (1) Department of Mathematics and Computer Science, International Christian University, Mitaka, Tokyo 181-8585, Japan |
| |
Abstract: | Many known distance-regular graphs have extra combinatorial regularities: One of them is t-homogeneity. A bipartite or almost bipartite distance-regular graph is 2-homogeneous if the number γ
i
= |{x | ∂(u, x) = ∂(v, x) = 1 and ∂(w, x) = i − 1}| (i = 2, 3,..., d) depends only on i whenever ∂(u, v) = 2 and ∂(u, w) = ∂(v, w) = i. K. Nomura gave a complete classification of bipartite and almost bipartite 2-homogeneous distance-regular graphs. In this
paper, we generalize Nomura’s results by classifying 2-homogeneous triangle-free distance-regular graphs. As an application,
we show that if Γ is a distance-regular graph of diameter at least four such that all quadrangles are completely regular then
Γ is isomorphic to a binary Hamming graph, the folded graph of a binary Hamming graph or the coset graph of the extended binary
Golay code of valency 24. We also consider the case Γ is a parallelogram-free distance-regular graph.
This research was partially supported by the Grant-in-Aid for Scientific Research (No.17540039), Japan Society of the Promotion
of Science. |
| |
Keywords: | Distance-regular graph association scheme homogeneity completely regular code |
本文献已被 SpringerLink 等数据库收录! |
|