zbMATH — the first resource for mathematics

The induced path function, monotonicity and betweenness. (English) Zbl 1225.05146
Summary: The geodesic interval function $$I$$ of a connected graph allows an axiomatic characterization involving axioms on the function only, without any reference to distance, as was shown by L. Nebeský [Czech. Math. J. 44, No.1, 173-178 (1994; Zbl 0808.05046)]. Surprisingly, L. Nebeský [Math. Bohem. 127, No. 3, 397–408 (2002; Zbl 1003.05063)] showed that, if no further restrictions are imposed, the induced path function $$J$$ of a connected graph $$G$$ does not allow such an axiomatic characterization. Here $$J(u,v)$$ consists of the set of vertices lying on the induced paths between $$u$$ and $$v$$. This function is a special instance of a transit function.
In this paper we address the question what kind of restrictions could be imposed to obtain axiomatic characterizations of $$J$$. The function $$J$$ satisfies betweenness if $$w \in J(u,v)$$, with $$w \neq u$$, implies $$u \notin J(w,v)$$ and $$x \in J(u,v)$$ implies $$J(u,x) \subseteq J(u,v)$$. It is monotone if $$x,y \in J(u,v)$$ implies $$J(x,y) \subseteq J(u,v)$$. In the case where we restrict ourselves to functions $$J$$ that satisfy betweenness, or monotonicity, we are able to provide such axiomatic characterizations of $$J$$ by transit axioms only. The graphs involved can all be characterized by forbidden subgraphs.

MSC:
 05C38 Paths and cycles 03C13 Model theory of finite structures
Full Text:
References:
 [1] Calder, J., Some elementary properties of interval convexities, J. London math. soc., 3, 422-428, (1971) · Zbl 0228.52001 [2] 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 [3] Changat, M.; Mathew, J., Interval monotone graphs: minimal path convexity, (), 87-90 · Zbl 0957.05061 [4] Changat, M.; Mathew, J., Induced path transit function, monotone and Peano axioms, Discrete math., 286, 185-194, (2004) · Zbl 1056.05044 [5] Changat, M.; Mathew, J., A characterization of $$J$$-monotone graphs, (), 47-55 [6] Changat, M.; Mulder, H.M.; Sierksma, G., Convexities related to path properties on graphs, Discrete math., 290, 117-131, (2005) · Zbl 1058.05043 [7] Dragan, F.; Nicolai, F.; Brandstädt, A., Convexity and $$H H D$$-free graphs, SIAM. J. discrete math., 12, 1, 119-135, (1999) · Zbl 0916.05060 [8] Duchet, P., Convexity in combinatorial structures, Rend. circ. mat. Palermo (2) suppl., 14, 261-293, (1987) [9] Duchet, P., Convex sets in graphs II. minimal path convexity, J. combin. theory ser. B., 44, 307-316, (1988) · Zbl 0672.52001 [10] Duchet, P., Discrete convexity: retractions, morphisms and partition problem, (), 10-18 · Zbl 0957.05030 [11] Farber, M.; Jamison, R.E., Convexity in graphs and hypergraphs, SIAM J. algebr. discrete methods, 7, 433-444, (1986) · Zbl 0591.05056 [12] Jamison, B.; Olariu, S., On the semi-perfect elimination, Adv. appl. math., 9, 364-376, (1988) · Zbl 0684.05020 [13] R.E. Jamison-Waldner, A perspective on abstract convexity: Classifying alignments by varieties, in: D.C. Kay and M. Breen (Eds.), Convexity and Related Combinatorial Geometry. Proceedings of 2nd Oklahoma Conf., New York, 1982, pp. 113-150 · Zbl 0482.52001 [14] Klavžar, S.; Mulder, H.M., Median graphs: characterizations, location theory and related structures, J. combin. math. combin. comput., 30, 103-127, (1999) · Zbl 0931.05072 [15] Mollard, M., Interval-regularity does not lead to interval monotonocity, Discrete math., 118, 233-237, (1993) · Zbl 0784.05040 [16] Morgana, M.A.; Mulder, H.M., The induced path convexity, betweenness and svelte graphs, Discrete math., 254, 349-370, (2002) · Zbl 1003.05090 [17] Mulder, H.M., () [18] Mulder, H.M., Transit functions on graphs (and posets), (), 117-130 · Zbl 1166.05019 [19] Mulder, H.M.; Nebeský, L., Axiomatic characterization of the interval function, European J. combin., 30, 1172-1185, (2009) · Zbl 1205.05074 [20] Nebeský, L., Characterization of the interval function of a connected graph, Czechoslovak math. J., 44, 173-178, (1994) · Zbl 0808.05046 [21] Nebeský, L., Characterizing the interval function of a connected graph, Math. bohemica., 123, 137-144, (1998) · Zbl 0937.05036 [22] Nebeský, L., Characterization of the interval function of a (finite or infinite) connected graph, Czechoslovak math. J., 51, 635-642, (2001) · Zbl 1079.05505 [23] Nebeský, L., The induced paths in a connected graph and a ternary relation determined by them, Math. bohemica., 127, 397-408, (2002) · Zbl 1003.05063 [24] Nomora, K., A remark of mulder’s conjucture about interval regular graphs, Discrete math., 147, 307-311, (1995) · Zbl 0838.05104 [25] Rose, D.; Tarjan, R.E.; Luekar, G., Algorithmic aspects on vertex elimination on graphs, SIAM J. comput., 5, 266-283, (1976) · Zbl 0353.65019 [26] Sampathkumar, E., Convex sets in graphs, Indian J. pure appl. math., 15, 1065-1071, (1984) · Zbl 0563.52001 [27] E. Sampathkumar, B-Systems, in: S. Amaguram, B.D. Acharya, and E. Sampathkumar (Eds.), Graph Theory and its Applications, Proceedings of the National Workshop, Manonmaniam Sundaranar University, Tirunelbeli, 1996, pp. 173-185 [28] Tarjan, R.E.; Yannakakis, M., Simple linear time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce a cyclic hypergraphs, SIAM J. comput., 3, 566-579, (1984) · Zbl 0545.68062 [29] 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.