×

zbMATH — the first resource for mathematics

Axiomatic characterization of the interval function of a block graph. (English) Zbl 1371.05170
Summary: M. Sholander [Proc. Am. Math. Soc. 3, 369–381 (1952; Zbl 0047.05401); ibid. 5, 801–807 (1954; Zbl 0056.26101)] formulated an axiomatic characterization of the interval function of a tree with a partial proof. V. Chvátal et al. [Discrete Math. 311, No. 20, 2143–2147 (2011; Zbl 1235.05029)] gave a completion of this proof. In this paper we present a characterization of the interval function of a block graph using axioms on an arbitrary transit function \(R\). From this we deduce two new characterizations of the interval function of a tree.

MSC:
05C51 Graph designs and isomorphic decomposition
05C05 Trees
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bandelt, H. J.; Mulder, H. M., Pseudo-modular graphs, Discrete Math., 62, 245-260, (1986) · Zbl 0606.05053
[2] Burigana, L., Tree representation of betweenness relations defined by intersection and inclusion, Math. Social Sci., 185, 5-36, (2009) · Zbl 1178.91170
[3] Changat, M.; Klavžar, S.; Mulder, H. M., The all-paths transit function of a graph, Czech. Math. J., 51, 126, 439-448, (2001) · Zbl 0977.05135
[4] Changat, M.; Lakshmikuttyamma, A. K.; Mathews, J.; Peterin, I.; Narasimha-Shenoi, P. G.; Seethakuttyamma, G.; Špacapan, S., A forbidden subgraph characterization of some graph classes using betweenness axioms, Discrete. Math., 313, 951-958, (2013) · Zbl 1262.05106
[5] Changat, M.; Mathew, J., On triangle path convexity in graphs, Discrete Math., 206, 91-95, (1999) · Zbl 0929.05046
[6] Changat, M.; Mathew, J.; Mulder, H. M., Induced path transit function, betweenness and monotonicity, Electron. Notes Discrete Math., 15, 62-65, (2003) · Zbl 1259.05052
[7] Changat, M.; Mathew, J.; Mulder, H. M., Induced path function, monotonicity and betweenness, Discrete Appl. Math, 158, 426-433, (2010) · Zbl 1225.05146
[8] Changat, M.; Mulder, H. M.; Sierksma, G., Convexities related to path properties on graphs, Discrete Math., 290, 117-131, (2005) · Zbl 1058.05043
[9] Changat, M.; Prasanth, G. N.; Mathews, J., Triangle path transit functions, betweenness and pseudo-modular graphs, Discrete Math., 309, 1575-1583, (2009) · Zbl 1228.05190
[10] Chvátal, V.; Rautenbach, D.; Schäfer, P. M., Finite sholander trees, trees, and their betweenness, Discrete Math., 311, 2143-2147, (2011) · Zbl 1235.05029
[11] Duthie, W. D., Segments in ordered sets, (1940), Princeton University, 27 pp · Zbl 0028.00501
[12] Duthie, W. D., Segments of ordered sets, Trans. AMS, 51, 1-14, (1942) · Zbl 0028.00501
[13] Lakshmikuttyamma, A. K., Geodesic and induced path transit functions, their generalizations, betweenness axioms and related graph classes, (2013), University of Kerala Trivandrum, (Ph.D. Thesis)
[14] Morgana, M. A.; Mulder, H. M., The induced path convexity, betweenness and svelte graphs, Discrete Math., 254, 349-370, (2002) · Zbl 1003.05090
[15] Mulder, H. M., The structure of Median graphs, Discrete Math., 24, 197-204, (1978) · Zbl 0394.05038
[16] Mulder, H. M., The interval function of a graph, MC tract 132, (1980), Mathematisch Centrum Amsterdam · Zbl 0446.05039
[17] Mulder, H. M., Transit functions on graphs (and posets), (Changat, M.; Klavžar, S.; Mulder, H. M.; Vijayakumar, A., Convexity in Discrete Structures, Ramanujan Math. Soc. Lect. Notes Ser., vol. 5, (2008), Ramanujan Math. Soc. Mysore), 117-130 · Zbl 1166.05019
[18] Mulder, H. M.; Nebeský, L., Axiomatic characterization of the interval function of a graph, European J. Combin., 30, 1172-1185, (2009) · Zbl 1205.05074
[19] Mulder, H. M.; Schrijver, A., Median graphs and Helly hypergraphs, Discrete Math., 25, 41-50, (1979) · Zbl 0395.05058
[20] Nebeský, L., Graphic algebras, Comment. Math. Univ. Carolinae, 11, 533-544, (1970) · Zbl 0208.02701
[21] Nebeský, L., The induced paths in a connected graph and a ternary relation determined by them, Math. Bohem., 127, 397-408, (2002) · Zbl 1003.05063
[22] Nebeský, L., Characterization of the set of all shortest paths in a connected graph, Math. Boh., 119, 15-20, (1994) · Zbl 0807.05045
[23] Nebeský, L., Characterization of the interval function of a connected graph, Czech. Math. J., 44, 173-178, (1994) · Zbl 0808.05046
[24] Nebeský, L., A characterization of the interval function of a (finite or infinite) connected graph, Czech. Math. J., 51, 635-642, (2001) · Zbl 1079.05505
[25] Pitcher, E.; Smiley, M. F., Transitivities of betweenness, Transactions AMS, 52, 95-114, (1942) · Zbl 0060.06408
[26] Sholander, M., Trees, lattices, order, and betweenness, Proc. Amer. Math. Soc., 3, 369-381, (1952)
[27] Sholander, M., Medians and betweenness, Proc. Amer. Math. Soc., 5, 801-807, (1952) · Zbl 0056.26101
[28] van de Vel, M. L.J., Theory of convex structures, (1993), North Holland Amsterdam · Zbl 0785.52001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.