Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
graphs; distance; interval function; geodetic graphs
graphs; distance; interval function; geodetic graphs
Summary:
The interval function (in the sense of H. M. Mulder) is an important tool for studying those properties of a connected graph that depend on the distance between vertices. An axiomatic characterization of the interval function of a connected graph was published by Nebeský in 1994. In Section 2 of the present paper, a simpler and shorter proof of that characterization will be given. In Section 3, a characterization of geodetic graphs will be established; this characterization will utilize properties of the interval function.
References:
[1] H.-J. Bandelt, H. M. Mulder: Regular pseudo-median graphs. J. Graph Theory 12 (1988), 533–549. DOI 10.1002/jgt.3190120410 | MR 0968750
[2] H.-J. Bandelt, H. M. Mulder: Three interval conditions for graphs. Ars Combin. 29B (1990), 213–223. MR 1412877
[3] H.-J. Bandelt, H. M. Mulder, E. Wilkeit: Quasi-median graphs and algebras. J. Graph Theory 18 (1994), 681–703. DOI 10.1002/jgt.3190180705 | MR 1297190
[4] H. M. Mulder: The Interval Function of a Graph. Mathematical Centre Tracts 132, Mathematisch Centrum, Amsterdam, 1980. MR 0605838 | Zbl 0446.05039
[5] L. Nebeský: A characterization of the set of all shortest paths in a connected graph. Math. Bohem. 119 (1994), 15–20. MR 1303548
[6] L. Nebeský: A characterization of the interval function of a connected graph. Czechoslovak Math. J. 44 (1994), 173–178. MR 1257943
[7] L. Nebeský: A characterization of geodetic graphs. Czechoslovak Math. J. 45 (1995), 491–493. MR 1344515
[8] L. Nebeský: Characterizing the interval function of a connected graph. Math. Bohem. 123 (1998), 137–144. MR 1673965
[9] L. Nebeský: An algebraic characterization of geodetic graphs. Czechoslovak Math. J. 48 (1998), 701–710. DOI 10.1023/A:1022435605919 | MR 1658245
[10] O. Ore: Theory of Graphs. Amer. Math. Soc. Colloq. Publ. 38, Providence, R. I., 1962. MR 0150753 | Zbl 0105.35401
Search
Partner of
