Distance-regular graphs with \(\Gamma(x) \simeq 3* K_{a+1}\)
type: Item
instance of: scholarly article
title: Distance-regular graphs with \(\Gamma(x) \simeq 3* K_{a+1}\)
zbMATH Open document ID: 0842.05029
DOI: 10.1016/0195-6698(95)90006-3
author: Norio Yamazaki
published in: European Journal of Combinatorics
publication date: 1996-07-28T00:00:00Z
review text: Let \(\Gamma\) be a connected graph and \(\alpha\), \(\beta\), \(x\), \(y\), \(z\) its vertices. Let \(\delta(\alpha, \beta)= i\) be a distance between \(\alpha\), \(\beta\). The graph \(\Gamma\) is said to be distance-regular if for each \(i\) the cardinalities \(c_i(\alpha, \beta)\) (\(a_i(\alpha, \beta)\), \(b_i(\alpha, \beta)\) resp.) of all vertices \(x\) (\(y\), \(z\) resp.) for which \[ \begin{alignedat}{2} \delta(\alpha, x) & = i- 1, &&\qquad \delta(\beta, x) = 1,\\ \delta(\alpha, y) & = i, &&\qquad \delta(\beta, y)= 1,\\ \delta(\alpha, z) & = i+ 1, &&\qquad \delta(\beta, z)= 1\end{alignedat} \] depend only on \(i\). The distance-regular graphs were studied recently e.g. by \textit{A. E. Brower}, \textit{A. M. Cohen} and \textit{A. Neumaier} (1989; Zbl 0747.05073)] and by \textit{H. Suzuki} (1994). The distance-biregular (bipartite) graphs were studied by \textit{B. Mohar} and \textit{J. Shawe-Taylor} (1985). The author investigates a special type of distance-regular graphs \(\Gamma\) which satisfy the following condition: For every \(\alpha\), \(\beta\) in \(\Gamma\) with \(\delta(\alpha, \beta)= 1\), the subgraph induced by the vertices \(x\) for which \[ \delta(\alpha, x)= \delta(\beta, x)= 1\tag{1} \] is a complete graph or an empty graph. In this case the neighborhood \(\Gamma(\alpha)\) of every vertex \(\alpha\) of \(\Gamma\) (i.e. the set of all vertices for which \(\delta(\alpha, x)= 1\)) is a disjoint union of \(m\) complete graphs \(K_{a+ 1}\) (\(a\) is the cardinality of all vertices \(x\) for which the equalities (1) hold). In the author's notation, such neighborhood \(\Gamma(\alpha)\) is denoted \(m* K_{a+ 1}\). He uses also the notation \(r(\Gamma)\) for the number of all \(i\), for which \((c_i, a_i, b_i)= (c_1, a_1, b_1)\). The main result of the paper is the following: Let \(\Gamma\) be a distance-regular graph with \(\Gamma(x)= 3* K_{a+ 1}\) for all \(x\in \Gamma\) and \(a\geq 2\). If \(d\geq r(\Gamma)+ 3\), then \(\Gamma\) is a distance-2 …
reviewed by: M.Koman
Mathematics Subject Classification ID: 05C12
Mathematics Subject Classification ID: 05E30
zbMATH DE Number: 798916
zbMATH Keywords: connected graph
zbMATH Keywords: distance
zbMATH Keywords: complete graphs
zbMATH Keywords: distance-regular graph
zbMATH Keywords: girths
MaRDI profile type: Publication
full work available at URL: 0195-6698(95)90006-3
OpenAlex ID: W159717946
cites work: Q3218140
cites work: On distance-regular graphs with fixed valency. II
cites work: A new 5‐arc‐transitive cubic graph
cites work: Cubic Distance-Regular Graphs
cites work: A remark on the intersection arrays of distance-regular graphs
cites work: Q3992965
cites work: A circuit chasing technique in a distance-regular graph with triangles
cites work: Distance-regular graphs of valency 6 and \(a_1=1\)
cites work: Bipartite distance-regular graphs of valency three
cites work: Q3344016
cites work: Distance-biregular graphs with 2-valent vertices and distance regular line graphs
cites work: On distance-biregular graphs of girth divisible by four
description: scientific article; zbMATH DE number 798916