Axiomatic characterization of the interval function of a graph. (English) Zbl 1205.05074

Mulder, Henry Martyn; Nebeský, Ladislav

Eur. J. Comb. 30, No. 5, 1172-1185 (2009).

Summary: A fundamental notion in metric graph theory is that of the interval function \(I : V\;times V \rightarrow 2^V-\{\emptyset\}\) of a (finite) connected graph \(G = (V,E)\), where \(I(u,v) = \{w \mid d(u,w)+d(w,v)=d(u,v)\}\) is the interval between \(u\) and \(v\). An obvious question is whether \(I\) can be characterized in a nice way amongst all functions \(F : V \times V \rightarrow 2^V-\{\emptyset \}\). This was done in [L. Nebeský, “A characterization of the interval function of a connected graph,” Czech. Math. J. 44, No.1, 173–178 (1994; Zbl 0808.05046); L. Nebeský, “Characterizing the interval function of a connected graph,” Math. Bohem. 123, No.2, 137–144 (1998; Zbl 0937.05036); L. Nebeský, “The interval function of a connected graph and a characterization of geodetic graph,” Math. Bohem. 126, No.1, 247–254 (2001; Zbl 0977.05045)] by axioms in terms of properties of the functions \(F\). The authors of the present paper, in the conviction that characterizing the interval function belongs to the central questions of metric graph theory, return here to this result again. In this characterization the set of axioms consists of five simple, and obviously necessary, axioms, already presented in [H.M. Mulder, “The interval function of a graph,” in: Math. Centre Tracts 132, Amsterdam: Mathematisch Centrum (1980; Zbl 0446.05039)], plus two more complicated axioms. The question arises whether the last two axioms are really necessary in the form given or whether simpler axioms would do the trick. This question turns out to be non-trivial. The aim of this paper is to show that these two supplementary axioms are optimal in the following sense. The functions satisfying only the five simple axioms are studied extensively. Then the obstructions are pinpointed why such functions may not be the interval function of some connected graph. It turns out that these obstructions occur precisely when either one of the supplementary axioms is not satisfied. It is also shown that each of these supplementary axioms is independent of the other six axioms. The presented way of proving the characterizing theorem allows us to find two new separate “intermediate” results. In addition some new characterizations of modular and median graphs are presented. As shown in the last section the results of this paper could provide a new perspective on finite connected graphs.

MSC:

05C12

Distance in graphs

Keywords:

metric graph theory; interval function

Citations:

Zbl 0808.05046; Zbl 0937.05036; Zbl 0977.05045; Zbl 0446.05039

References:

[1]	Avann, S. P., Metric ternary distributive semi-lattices, Proc. Amer. Math. Soc., 12, 407-414 (1961) · Zbl 0099.02201
[2]	Bandelt, H. J.; Mulder, H. M., Pseudo-modular graphs, Discrete Math., 62, 245-260 (1986) · Zbl 0606.05053
[3]	Changat, M.; Klavžar, S.; Mulder, H. M., The all-paths transit function of a graph, Czechoslovak Math. J., 51, 126, 439-447 (2001) · Zbl 0977.05135
[4]	Hedlíková, J., Ternary spaces, media, and Chebyshev sets, Czechoslovak Math. J., 33, 108, 373-389 (1983) · Zbl 0544.51011
[5]	Howorka, E., Betweenness in graphs, Abstracts Amer. Math. Soc., 2, *783-06-5 (1982)
[6]	Kay, D. C.; Chartrand, G., A characterization of certain ptolemaic graphs, Canadian J. Math., 17, 342-346 (1965) · Zbl 0139.17301
[7]	Morgana, M. A.; Mulder, H. M., The induced path convexity, betweenness, and svelte graphs, Discrete Math., 254, 349-379 (2002) · Zbl 1003.05090
[8]	Mulder, H. M., The structure of median graphs, Discrete Math., 24, 197-204 (1978) · Zbl 0394.05038
[9]	Mulder, H. M., (The Interval Function of a Graph. The Interval Function of a Graph, Math. Centre Tracts, vol. 132 (1980), Math. Centre: Math. Centre Amsterdam, Netherlands) · Zbl 0446.05039
[10]	Mulder, H. M., Transit functions on graphs (and posets), (Changat, M.; Klavžar, S.; Mulder, H. M.; Vijayakumar, A., Convexity in Discrete Structures. Convexity in Discrete Structures, RMS Lecture Notes Series, vol. 5 (2008)), 117-130 · Zbl 1166.05019
[11]	Mulder, H. M.; Schrijver, A., Median graphs and Helly hypergraphs, Discrete Math., 25, 41-50 (1979) · Zbl 0395.05058
[12]	Nebeský, L., Median graphs, Comment. Math. Univ. Carolin., 12, 317-325 (1971) · Zbl 0215.34001
[13]	Nebeský, L., A characterization of the interval function of a connected graph, Czechoslovak Math. J., 44, 119, 173-178 (1994) · Zbl 0808.05046
[14]	Nebeský, L., Characterizing the interval function of a connected graph, Math. Bohem., 123, 137-144 (1998) · Zbl 0937.05036
[15]	Nebeský, L., A characterization of the interval function of a (finite or infinite) connected graph, Czechoslovak Math. J., 51, 126, 635-642 (2001) · Zbl 1079.05505
[16]	Nebeský, L., The interval function of a connected graph and a characterization of geodetic graph, Math. Bohem., 126, 247-254 (2001) · Zbl 0977.05045
[17]	Nebeský, L., Intervals and steps in a connected graph, Discrete Math., 286, 151-156 (2004) · Zbl 1053.05041
[18]	Nebeský, L., The interval function of a connected graph and road systems, Discrete Math., 307, 2067-2073 (2007) · Zbl 1119.05033
[19]	E. Sampathkumar, B-systems, in: S. Arumugam, B.D. Acharya, E. Sampathkumar (Eds.), Graph Theory and its Applications, Proceedings of the National Workshop, Manonmaniam Sundaranar University, Tirunelveli, India, 1996; E. Sampathkumar, B-systems, in: S. Arumugam, B.D. Acharya, E. Sampathkumar (Eds.), Graph Theory and its Applications, Proceedings of the National Workshop, Manonmaniam Sundaranar University, Tirunelveli, India, 1996
[20]	Sholander, M., Trees, lattices, order, and betweenness, Proc. Amer. Math. Soc., 3, 369-381 (1952) · Zbl 0047.05401
[21]	van de Vel, M., Theory of Convex Structures (1993), North Holland: North Holland Amsterdam, Netherlands · Zbl 0785.52001
[22]	E.R. Verheul, Multimedians in metric and normed spaces, Ph.D. Thesis, 1991. Also published as CWI Tract 91, CWI, Amsterdam, Netherlands 1993; E.R. Verheul, Multimedians in metric and normed spaces, Ph.D. Thesis, 1991. Also published as CWI Tract 91, CWI, Amsterdam, Netherlands 1993