ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory


Discussiones Mathematicae Graph Theory 30(4) (2010) 671-685
DOI: 10.7151/dmgt.1522


Manoj Changat,  Joseph Mathews

Department of Futures Studies
University of Kerala, Trivandrum, India

Iztok Peterin

Institute of Mathematics and Physics, FEECS
University of Maribor, Smetanova 17, 2000 Maribor, Slovenia

Prasanth G. Narasimha-Shenoi

Department of Mathematics, Government College, Chittur
Palakkad - 678 104, India


n-ary transit functions are introduced as a generalization of binary (2-ary) transit functions. We show that they can be associated with convexities in natural way and discuss the Steiner convexity as a natural n-ary generalization of geodesicaly convexity. Furthermore, we generalize the betweenness axioms to n-ary transit functions and discuss the connectivity conditions for underlying hypergraph. Also n-ary all paths transit function is considered.

Keywords: n-arity, transit function, betweenness, Steiner convexity.

2000 Mathematics Subject Classification: 52A01, O5C12.


[1] B. Bresar, M. Changat, J. Mathews, I. Peterin, P.G. Narasimha-Shenoi and A. Tepeh Horvat, Steiner intervals, geodesic intervals, and betweenness, Discrete Math. 309 (2009) 6114-6125, doi: 10.1016/j.disc.2009.05.022.
[2] M. Changat, S. Klavžar and H.M. Mulder, The All-Paths Transit Function of a Graph, Czechoslovak Math. J. 51 (126) (2001) 439-448.
[3] M. Changat and J. Mathew, Induced path transit function, monotone and Peano axioms, Discrete Math. 286 (2004) 185-194, doi: 10.1016/j.disc.2004.02.017.
[4] M. Changat and J. Mathew, Characterizations of J-monotone graphs, in: Convexity in Discrete Structures (M. Changat, S. Klavžar, H.M. Mulder, A. Vijayakumar, eds.), Lecture Notes Ser. 5, Ramanujan Math. Soc. (2008) 47-55.
[5] M. Changat, J. Mathew and H.M. Mulder, Induced path function, betweenness and monotonicity, Discrete Appl. Math. 158 (2010) 426-433, doi: 10.1016/j.dam.2009.10.004.
[6] M. Changat, J. Mathew and H.M. Mulder, Induced path transit function, betweenness and monotonicity, Elect. Notes Discrete Math. 15 (2003).
[7] M. Changat, H.M. Mulder and G. Sierksma, Convexities Related to Path Properties on Graphs, Discrete Math. 290 (2005) 117-131, doi: 10.1016/j.disc.2003.07.014.
[8] M. Changat, P.G. Narasimha-Shenoi and I.M. Pelayo, The longest path transit function and its betweenness, to appear in Util. Math.
[9] P. Duchet, Convexity in combinatorial structures, Rend. Circ. Mat. Palermo (2) Suppl. 14 (1987) 261-293.
[10] P. Duchet, Convex sets in graphs II. Minimal path convexity, J. Combin. Theory (B) 44 (1988) 307-316, doi: 10.1016/0095-8956(88)90039-1.
[11] P. Duchet, Discrete convexity: retractions, morphisms and partition problem, in: Proceedings of the conference on graph connections, India, (1998), Allied Publishers, New Delhi, 10-18.
[12] P. Hall, On representation of subsets, J. Lon. Mat. Sc. 10 (1935) 26-30, doi: 10.1112/jlms/s1-10.37.26.
[13] M.A. Morgana and H.M. Mulder, The induced path convexity, betweenness and svelte graphs, Discrete Math. 254 (2002) 349-370, doi: 10.1016/S0012-365X(01)00296-5.
[14] H.M. Mulder, The Interval Function of a Graph. Mathematical Centre Tracts 132, Mathematisch Centrum (Amsterdam, 1980).
[15] H.M. Mulder, Transit functions on graphs (and posets), in: Convexity in Discrete Structures (M. Changat, S. Klavžar, H.M. Mulder, A. Vijayakumar, eds.), Lecture Notes Ser. 5, Ramanujan Math. Soc. (2008) 117-130.
[16] L. Nebeský, A characterization of the interval function of a connected graph, Czechoslovak Math. J. 44(119) (1994) 173-178.
[17] L. Nebeský, A Characterization of the interval function of a (finite or infinite) connected graph, Czechoslovak Math. J. 51(126) (2001) 635-642.
[18] E. Sampathkumar, Convex sets in graphs, Indian J. Pure Appl. Math. 15 (1984) 1065-1071.
[19] M.L.J. van de Vel, Theory of Convex Structures (North Holland, Amsterdam, 1993).

Received 11 November 2009
Accepted 2 March 2010