Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
connected graphs; distance; steps; geodetically smooth graphs
connected graphs; distance; steps; geodetically smooth graphs
Summary:
If $G$ is a connected graph with distance function $d$, then by a step in $G$ is meant an ordered triple $(u, x, v)$ of vertices of $G$ such that $d(u, x) = 1$ and $d(u, v) = d(x, v) + 1$. A characterization of the set of all steps in a connected graph was published by the present author in 1997. In Section 1 of this paper, a new and shorter proof of that characterization is presented. A stronger result for a certain type of connected graphs is proved in Section 2.
References:
[1] H.-J. Bandelt and H. M. Mulder: Pseudo-modular graphs. Discrete Math. 62 (1986), 245–260. DOI 10.1016/0012-365X(86)90212-8 | MR 0866940
[2] G. Chartrand and L. Lesniak: Graphs & Digraphs. Third edition. Chapman & Hall, London, 1996. MR 1408678
[3] S. Klavžar and H. M. Mulder: Median graphs: characterizations, location theory and related structures. J. Combin. Math. Combin. Comput. 30 (1999), 103–127. MR 1705337
[4] H. M. Mulder: The interval function of a graph. Math. Centre Tracts 132, Math. Centre, Amsterdam, 1980. MR 0605838 | Zbl 0446.05039
[5] H. M. Mulder and L. Nebeský: Modular and median signpost systems and their underlying graphs. Discuss. Math. Graph Theory 23 (2003), 309–32444. DOI 10.7151/dmgt.1204 | MR 2070159
[6] L. Nebeský: Geodesics and steps in a connected graph. Czechoslovak Math. J. 47 (122) (1997), 149–161. DOI 10.1023/A:1022404624515 | MR 1435613
[7] L. Nebeský: An axiomatic approach to metric properties of connected graphs. Czechoslovak Math. J. 50 (125) (2000), 3–14. DOI 10.1023/A:1022472700080 | MR 1745453
[8] L. Nebeský: A theorem for an axiomatic approach to metric properties of graphs. Czechoslovak Math. J. 50 (125) (2000), 121–133. DOI 10.1023/A:1022401506441 | MR 1745467
[9] L. Nebeský: A tree as a finite nonempty set with a binary operation. Math. Bohem. 125 (2000), 455–458. MR 1802293
Search
Partner of
