Intervals and steps in a connected graph

DOI10.1016/J.DISC.2003.11.056MaRDI QIDQ1883264zbMATH OpenOpenAlexFDO

Authors Ladislav Nebeský

Publication date 1 October 2004

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2003.11.056

zbMATH Keywords

distancegeodesicinterval functionstep

Mathematics Subject Classification ID

Distance in graphs (05C12) Connectivity (05C40)

Review text

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.

Recommendations

• On Properties of a Graph that Depend on its Distance Function
• An axiomatic approach to metric properties of connected graphs
• A Characterization of the Interval Function of a (Finite or Infinite) Connected Graph
• The interval function of a connected graph and a~characterization of geodetic graphs
• Geodesics and steps in a connected graph

Cites work

• A characterization of the interval function of a connected graph
• A Helly theorem in weakly modular space
• A theorem for an axiomatic approach to metric properties of graphs
• A tree as a finite nonempty set with a binary operation
• An axiomatic approach to metric properties of connected graphs
• Geodesics and steps in a connected graph
• scientific article; zbMATH DE number 3697163 (Why is no real title available?)
• scientific article; zbMATH DE number 1055145 (Why is no real title available?)
• scientific article; zbMATH DE number 1449370 (Why is no real title available?)
• Modular and median signpost systems and their underlying graphs
• Modular Interval Spaces
• On Properties of a Graph that Depend on its Distance Function
• The interval function of a connected graph and a~characterization of geodetic graphs

Cited in

(11)

• Axiomatic characterization of the interval function of a graph
• Betweenness in graphs: a short survey on shortest and induced path betweenness
• On subbetweennesses of trees: hardness, algorithms, and characterizations
• The interval function of a connected graph and a~characterization of geodetic graphs
• scientific article; zbMATH DE number 3843789 (Why is no real title available?)
• On Properties of a Graph that Depend on its Distance Function
• On certain extensions of intervals in graphs
• Guides and shortcuts in graphs
• Geodesics and steps in a connected graph
• A theorem for an axiomatic approach to metric properties of graphs
• Finite Sholander trees, trees, and their betweenness

This page was built for publication: Intervals and steps in a connected graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1883264)