Almost 2-Homogeneous Graphs and Completely Regular Quadrangles
| 详细信息 | 推荐本文 | |
- 作者：Hiroshi Suzuki
- 关键词：Distance ; regular graph ; association scheme ; homogeneity ; completely regular code
- 刊名：Graphs and Combinatorics
- 出版时间：November, 2008
- 出版年：2008
- 期刊代码：63_0911-0119
- 类别：mat
- 卷：24
- 期：6
- 页码：571-585
- 数据来源：sp
摘要
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.