Geodesics and steps in a connected graph

From MaRDI portal





A step in a connected undirected graph \(G\) is an ordered triple of vertices \((u,v,x)\) such that \(d(u,v)=1\) and \(d(u,x)=d(v,x)+1,\) where \(d\) denotes the distance. For a ternary relation \(T\) on a set \(V\) the graph \(\Gamma (V,T)\) is defined so that its vertex set is \(V\) and two vertices \(u\), \(v\) are adjacent in it if and only if there exists \(x\in V\) such that \((u,v,x) \in T\) or \((v,u,x)\in T.\) The main theorem gives a necessary and sufficient condition for a ternary relation \(T\) on \(V\) with the connected graph \(\Gamma (V,T)\) to be the set of all steps in \(\Gamma (V,T).\) This condition is formulated in the form of eight axioms. An analogous necessary and sufficient condition is stated for an ordered \(n\)-tuple (with arbitrary \(n\)) to determine a geodesic (the shortest path between two given vertices).











This page was built for publication: Geodesics 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 Q4209985)