Article

Full entry | PDF   (0.2 MB)
Summary:
We say that a binary operation $*$ is associated with a (finite undirected) graph $G$ (without loops and multiple edges) if $*$ is defined on $V(G)$ and $uv\in E(G)$ if and only if $u\ne v$, $u * v=v$ and $v*u=u$ for any $u$, $v\in V(G)$. In the paper it is proved that a connected graph $G$ is geodetic if and only if there exists a binary operation associated with $G$ which fulfils a certain set of four axioms. (This characterization is obtained as an immediate consequence of a stronger result proved in the paper).
References:
[1] M. Behzad, G. Chartrand and L. Lesniak-Foster: Graphs & Digraphs. Prindle, Weber & Schmidt, Boston, 1979. MR 0525578
[2] F. Harary: Graph Theory. Addison-Wesley, Reading (Mass.), 1969. MR 0256911 | Zbl 0196.27202
[3] H. M. Mulder: The Interval Function of a Graph. Mathematisch Centrum. Amsterdam, 1980. MR 0605838 | Zbl 0446.05039
[4] L. Nebeský: A characterization of the set of all shortest paths in a connected graph. Mathematica Bohemica 119 (1994), 15–20. MR 1303548
[5] L. Nebeský: A characterization of geodetic graphs. Czechoslovak Math. Journal 45 (120) (1995), 491–493. MR 1344515
[6] L. Nebeský: Geodesics and steps in a connected graph. Czechoslovak Math. Journal 47 (122) (1997), 149–161. DOI 10.1023/A:1022404624515 | MR 1435613

Partner of