A distance-regular graph with bipartite geodetically closed subgraphs. (Q1873771)

From MaRDI portal
scientific article
Language Label Description Also known as
English
A distance-regular graph with bipartite geodetically closed subgraphs.
scientific article

    Statements

    A distance-regular graph with bipartite geodetically closed subgraphs. (English)
    0 references
    0 references
    27 May 2003
    0 references
    Let \(\Gamma\) be a distance-regular graph of diameter \(d\), and \(t\) be an integer with \(2 \leq t \leq d-1\) such that \(a_{t-1} = 0\) (if \(u\) and \(v\) are two vertices of \(\Gamma\) at distance \(i\), then \(a_i\) is the cardinality of the set of neighbours of \(v\) which are at distance \(i\) from \(u\)). For every pair \((u,v)\) of vertices, let \(\Pi(u,v)\) be the subgraph induced by the vertices lying on shortest paths between \(u\) and \(v\). The author proves that if \(\Pi(u,v)\) is a bipartite geodetically closed subgraph for some pair \((u,v)\) of vertices at distance \(t\), then \(\Pi(x,y)\) is a bipartite geodetically closed subgraph for every pair \((x,y)\) of vertices at distance at most \(t\). Moreover, he shows that for every such pair \((x,y)\) the graph \(\Pi(x,y)\) is either a path, a polygon, a hypercube or an \((n,m)\)-projective incidence graph (that is, the graph with set of vertices the set of \(m\)-subsets and \(m+1\)-subsets of a fixed \(n\)-set, two vertices \(u, v\) being adjacent if \(u \neq v\) and \(u \subset v\) or \(v \subset u\)). In the case that \(t = d\) the author determines the graph \(\Gamma\), as well. It is either a polygon, the \(d\)-cube, the folded \((2d+1)\)-cube, the odd graph \(O_{d+1}\) or the doubled odd graph \(2O_{{d+1}/2}\).
    0 references
    0 references
    0 references
    0 references
    0 references
    distance-regular graph
    0 references
    geodetically closed subgraph
    0 references
    hypercube
    0 references
    odd graph
    0 references
    Kneser graph
    0 references
    projective incidence graph
    0 references