Intervals and steps in a connected graph (Q1883264)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Intervals and steps in a connected graph |
scientific article |
Statements
Intervals and steps in a connected graph (English)
0 references
1 October 2004
0 references
Let \(d\) be a distance function of a finite connected graph \(G\) with vertex set \(V\). The \(u\)-\(v\) interval in \(G\) \((u,v\in V)\) is the set \(\{x\in V\mid d(u,x)+d (x,y)=d(u,v)\}\). The interval function of \(G\) is the mapping \(I\) of \(V\times V\) into the power set of \(V\) such that \(I(u,v)\) is the \(u\)-\(v\) interval of \(G\). A step in \(G\) is an ordered triple \((u,v,w)\) where \(u,v,w\in V\), \(d(u,v)=1\), \(d(v,w)=d(u,w)-1\). This paper is a review of author's characterization of intervals and steps in a connected graph [Czech Math. J. 44, No. 1, 173--178 (1994; Zbl 0808.05046); Czech Math. J. 47, No. 1, 149--161 (1997; Zbl 0898.05041)]. Some small results and short proofs are new.
0 references
distance
0 references
geodesic
0 references
interval function
0 references
step
0 references