A distance-regular graph with strongly closed subgraphs (Q1610682)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A distance-regular graph with strongly closed subgraphs |
scientific article |
Statements
A distance-regular graph with strongly closed subgraphs (English)
0 references
20 August 2002
0 references
Let \(\Gamma\) be a simple connected graph with diameter \(d\). For a vertex \(u\) of \(\Gamma\) denote by \(\Gamma_j(u)\) the set of vertices which are at distance \(j\) from \(u\). The graph \(\Gamma\) is called distance-regular if for any vertices \(u\) and \(v\) of \(\Gamma\) at distance \(i\) the numbers \(c_i= |\Gamma_{i-1}(u)\cap \Gamma_1(v)|\) and \(a_i= |\Gamma_i(u)\cap \Gamma_1(v)|\) and \(b_{i-1}= |\Gamma_i(u)\cap \Gamma_1(v)|\) do not depend on the choice of \(u\) and \(v\). The graph \(\Gamma\) is called strongly regular if \(c_i\), \(a_i\), \(b_{i-1}\) exist for all \(i\) with \(1\leq i\leq d\). The number \(k= b_0\) is called the valency of \(\Gamma\). The author assumes \(\Gamma\) is a distance-regular graph of diameter \(d\), valency \(k\) and \(r= \max\{i\mid (c_i,b_i)= (c_1, b_1)\}\), and proves that if for any integer \(q\) with \(r+ 1\leq q\leq d-1\), and if for any pair of vertices at distance \(q\), there exists a strongly closed subgraph of diameter \(q\) containing them, then for any integer \(i\) with \(1\leq i\leq q\) and for any pair of vertices at distance \(i\), there exists a strongly closed subgraph of diameter \(i\) containing them. The author also obtains the result that if \(r\geq 2\), then \(c_{2r+3}\neq 1\) and \(d\leq k^2(r+1)\).
0 references
distance-regular graph
0 references
strongly closed subgraph
0 references