Distance-regular graphs with (x) 3* K_a+1

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 graph of a distance-biregular graph with vertices of valency 3. This theorem is a result of detailed investigations of two types of graphs with odd and even girths.

Recommendations

Cites work

Cited in

(21)

This page was built for publication: Distance-regular graphs with \(\Gamma(x) \simeq 3* K_{a+1}\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1898055)