Cycle transit function and betweenness

Document Type : Original paper

Authors

1 Department of Futures Studies University of Kerala Karyavattom

2 Department of Futures Studies University of Kerala Karyavattom Trivandrum

Abstract

Transit functions are introduced to study betweenness, intervals and convexity in an axiomatic setup on graphs and other discrete structures. Prime example of a transit function on graphs is the well studied interval function of a connected graph. In this paper, we study the Cycle transit function $\mathcal{C}( u,v)$ on graphs which is a transit function derived from the interval function. We study the betweenness properties and also characterize graphs in which the cycle transit function coincides with the interval function. We also characterize graphs where $|\mathcal{C}( u,v)\cap \mathcal{C}( v,w) \cap \mathcal{C}( u,w)|\le 1$ as an analogue of median graphs.

Keywords

Main Subjects

References

[1] H.-J. Bandelt and V. Chepoi, Decomposition and l1-embedding of weakly median graphs, European J. Combin. 21 (2000), no. 6, 701–714.
[2] B. Breser, M. Changat, H.M. Mulder, and . Novic, Prefiber transit function on graphs, (in preparation).
[3] M. Changat, H.M. Mulder, and G. Sierksma, Convexities related to path properties on graphs, Discrete Math. 290 (2005), no. 2-3, 117–131.
[4] M. Changat, F.H. Nezhad, H. Mulder, and N. Narayanan, A note on the interval function of a disconnected graph, Discuss. Mathe. Graph Theory 38 (2018), no. 1, 39–48.
[5] M. Changat, G.N. Prasanth, and J. Mathews, Triangle path transit functions, betweenness and pseudo-modular graphs, Discrete Math. 309 (2009), no. 6, 1575–1583.
[6] V. Chepoi, Separation of two convex sets in convexity structures, J. Geom. 50 (1994), no. 1, 30–51.
[7] V.D. Chepoi, Isometric subgraphs of Hamming graphs and d-convexity, Cybernetics 24 (1988), no. 1, 6–11.
[8] H.M. Mulder, The interval function of a graph, MC Tract 132, Mathematisch Centrum, Amsterdam, 1980.
[9] H.M. Mulder, Transit functions on graphs (and posets), Convexity in Discrete Structures, Lecture Notes Ser. 5 (M. Changat, S. KlavĖ‡zar, H.M. Mulder, and A. Vijayakumar, eds.), Ramanujan Math. Soc., 2008, pp. 117–130.
[10] H.M. Mulder and L. Nebesk`y, Axiomatic characterization of the interval function of a graph, European J. Combin. 30 (2009), no. 5, 1172–1185.
[11] L. Nebeský, A characterization of the interval function of a connected graph, Czechoslovak Math. J. 44 (1994), no. 1, 173–178.
[12] L. Nebeský, A characterization of the set of all shortest paths in a connected graph,
Math. Bohem. 119 (1994), no. 1, 15–20.
[13] L. Nebeský, A characterization of geodetic graphs, Czechoslovak Math. J. 45 (1995), no. 3, 491–493.
[14] L. Nebeský, Characterizing the interval function of a connected graph, Math. Bohem. 123 (1998), no. 2, 137–44. 
[15] L. Nebeský, A new proof of a characterization of the set of all geodesics in a connected graph, Czechoslovak Math. J. 48 (1998), no. 4, 809–813.
[16] L. Nebeský, A characterization of the interval function of a (finite or infinite) connected graph, Czechoslovak Math. J. 51 (2001), no. 3, 635–642.
[17] N. Polat, Netlike partial cubes I. general properties, Discrete Math. 307 (2007), no. 22, 2704–2722.
 
Communications in Combinatorics and Optimization
Volume 8, Issue 4
December 2023
Pages 725-735

Files

Share

How to cite

Statistics