20090701
Axiomatic characterization of the interval function of a graph
Publication
Publication
European Journal of Combinatorics , Volume 30  Issue 5 p. 1172 1185
A fundamental notion in metric graph theory is that of the interval function I : V × V → 2  {0{combining long solidus overlay}} of a (finite) connected graph G = (V, E), where I (u, v) = {w {divides} 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 × V → 2  {0{combining long solidus overlay}}. This was done in [L. Nebeský, A characterization of the interval function of a connected graph, Czechoslovak Math. J. 44 (119) (1994) 173178; L. Nebeský, Characterizing the interval function of a connected graph, Math. Bohem. 123 (1998) 137144; L. Nebeský, The interval function of a connected graph and a characterization of geodetic graph, Math. Bohem. 126 (2001) 247254] 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, vol. 132, Math. Centre, Amsterdam, Netherlands, 1980], 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 nontrivial. 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.
Additional Metadata  

doi.org/10.1016/j.ejc.2008.09.007, hdl.handle.net/1765/14595  
European Journal of Combinatorics  
Organisation  Erasmus School of Economics 
Mulder, H, & Nebesky, L. (2009). Axiomatic characterization of the interval function of a graph. European Journal of Combinatorics, 30(5), 1172–1185. doi:10.1016/j.ejc.2008.09.007
