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
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
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