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
    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
    0 references
    distance-regular graph
    0 references
    strongly closed subgraph
    0 references