A distance-regular graph with bipartite geodetically closed subgraphs.
type: Item
instance of: scholarly article
title: A distance-regular graph with bipartite geodetically closed subgraphs.
zbMATH Open document ID: 1037.05050
DOI: 10.1016/S0195-6698(03)00014-3
author: Akira Hiraki
published in: European Journal of Combinatorics
publication date: 2003-05-27T00:00:00Z
review text: 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}\).
reviewed by: Barbara Baumeister
Mathematics Subject Classification ID: 05E30
Mathematics Subject Classification ID: 05C12
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 1917866
zbMATH Keywords: distance-regular graph
zbMATH Keywords: geodetically closed subgraph
zbMATH Keywords: hypercube
zbMATH Keywords: odd graph
zbMATH Keywords: Kneser graph
zbMATH Keywords: projective incidence graph
MaRDI profile type: Publication
cites work: Q3218140
cites work: Cubic Distance-Regular Graphs
cites work: Q3992965
cites work: The distance-regular graphs of valency four
cites work: The dual of Pasch's axiom
cites work: Characterization of H(n,q) by the parameters
cites work: A characterization of the doubled Grassmann graphs, the doubled Odd graphs, and the Odd graphs by strongly closed subgraphs
cites work: A new condition for distance-regular graphs
cites work: On subgraphs in distance-regular graphs
cites work: On uniformly geodetic graphs
cites work: Characterization of projective incidence structures
cites work: Classification of a class of distance-regular graphs via completely regular codes
cites work: On the existence of certain distance-regular graphs
cites work: On strongly closed subgraphs of highly regular graphs
cites work: Distance-regular graphs and (s,c,a,k)-graphs
Recommended article: Geodetically closed subgraphs in a distance-regular graph
Recommended article: A distance-regular graph with strongly closed subgraphs
Recommended article: Bipartite distance-regular graphs. I
Recommended article: Weak-geodetically closed subgraphs in distance-regular graphs
Recommended article: A characterization of bipartite distance-regular graphs
Recommended article: Distance biregular bipartite graphs
Recommended article: Bipartite distance-regular graphs. II
Recommended article: Distance-regular graphs with strongly regular subconstituents
Recommended article: Distance-regular subgraphs in a distance-regular graph. II
Recommended article: On subgraphs in distance-regular graphs
description: scientific article; zbMATH DE number 1917866