Parallelogram-free distance-regular graphs having completely regular strongly regular subgraphs

被引:0
作者
Hiroshi Suzuki
机构
[1] International Christian University,Department of Mathematics and Computer Science
来源
Journal of Algebraic Combinatorics | 2009年 / 30卷
关键词
Distance-regular graph; Association scheme; Homogeneity; Completely regular code;
D O I
暂无
中图分类号
学科分类号
摘要
Let Γ=(X,R) be a distance-regular graph of diameter d. A parallelogram of length i is a 4-tuple xyzw consisting of vertices of Γ such that ∂(x,y)=∂(z,w)=1, ∂(x,z)=i, and ∂(x,w)=∂(y,w)=∂(y,z)=i−1. A subset Y of X is said to be a completely regular code if the numbers \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\pi_{i,j}=|\Gamma_{j}(x)\cap Y|\quad (i,j\in \{0,1,\ldots,d\})$$\end{document} depend only on i=∂(x,Y) and j. A subset Y of X is said to be strongly closed if \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\{x\mid \partial(u,x)\leq \partial(u,v),\partial(v,x)=1\}\subset Y,\mbox{ whenever }u,v\in Y.$$\end{document} Hamming graphs and dual polar graphs have strongly closed completely regular codes. In this paper, we study parallelogram-free distance-regular graphs having strongly closed completely regular codes. Let Γ be a parallelogram-free distance-regular graph of diameter d≥4 such that every strongly closed subgraph of diameter two is completely regular. We show that Γ has a strongly closed subgraph of diameter d−1 isomorphic to a Hamming graph or a dual polar graph. Moreover if the covering radius of the strongly closed subgraph of diameter two is d−2, Γ itself is isomorphic to a Hamming graph or a dual polar graph. We also give an algebraic characterization of the case when the covering radius is d−2.
引用
收藏
页码:401 / 413
页数:12
相关论文
共 13 条
[1]  
Brouwer A.E.(2003)Width and dual width of subsets in polynomial association schemes J. Comb. Theory A 102 255-271
[2]  
Godsil C.D.(2007)Tight distance-regular graphs with respect to subsets of width two Eur. J. Comb. 28 61-74
[3]  
Koolen J.H.(1992)Completely regular codes Discrete Math. 106–107 353-360
[4]  
Martin W.J.(1990)Distance-regular graphs of Hamming type J. Comb. Theory B 50 160-167
[5]  
Hosoya R.(1995)On strongly closed subgraphs of highly regular graphs Eur. J. Comb. 16 197-220
[6]  
Suzuki H.(1996)Strongly closed subgraphs of a distance-regular graph with geometric girth five Kyushu J. Math. 50 371-384
[7]  
Neumaier A.(2005)The Terwilliger algebra associated with a set of vertices in a distance-regular graph J. Algebr. Comb. 22 5-38
[8]  
Nomura K.(2006)Classification of subsets with minimal width and dual width in Grassmann, bilinear forms and dual polar graphs J. Comb. Theory A 113 903-910
[9]  
Suzuki H.(1998)Weak-geodesically closed subgraphs in distance-regular graphs Graphs Comb. 14 275-304
[10]  
Suzuki H.(undefined)undefined undefined undefined undefined-undefined