Opuscula Math. 43, no. 3 (2023), 393-407
https://doi.org/10.7494/OpMath.2023.43.3.393
Opuscula Mathematica
Axiomatic characterizations of Ptolemaic and chordal graphs
Manoj Changat
Lekshmi Kamal K. Sheela
Prasanth G. Narasimha-Shenoi
Abstract. The interval function and the induced path function are two well studied class of set functions of a connected graph having interesting properties and applications to convexity, metric graph theory. Both these functions can be framed as special instances of a general set function termed as a transit function defined on the Cartesian product of a non-empty set \(V\) to the power set of \(V\) satisfying the expansive, symmetric and idempotent axioms. In this paper, we propose a set of independent first order betweenness axioms on an arbitrary transit function and provide characterization of the interval function of Ptolemaic graphs and the induced path function of chordal graphs in terms of an arbitrary transit function. This in turn gives new characterizations of the Ptolemaic and chordal graphs.
Keywords: interval function, betweenness axioms, Ptolemaic graphs, transit function, induced path transit function.
Mathematics Subject Classification: 05C12, 05C75.
- K. Balakrishnan, M. Changat, A.K. Lakshmikuttyamma, J. Mathew, H.M. Mulder, P.G. Narasimha-Shenoi, N. Narayanan, Axiomatic characterization of the interval function of a block graph 338 (2015), 885-894. https://doi.org/10.1016/j.disc.2015.01.004
- A. Brandstädt, V.B. Le, J.P. Spinrad, Graph Classes - A Survey, SIAM Monogr. J. Discrete Math., 1999.
- M. Changat, F. Hossein Nezhad, H.M. Mulder, N. Narayanan, A note on the interval function of a disconnected graph, Discuss. Math. Graph Theory 38 (2018), no. 1, 39-48.
- M. Changat, F. Hossein Nezhad, N. Narayanan, Axiomatic characterization of claw and paw-free graphs using graph transit functions, [in:] Conference on Algorithms and Disc. Appl. Math. Springer LNCS (2016), pp. 115-125.
- M. Changat, F. Hossein Nezhad, N. Narayanan, Axiomatic characterization of the interval function of a bipartite graph, [in:] Conference on Algorithms and Disc. Appl. Math. Springer LNCS (2017), 96-106.
- M. Changat, A.K. Lakshmikuttyamma, J. Mathew, I. Peterin, P.G. Narasimha-Shenoi, G. Seethakuttyamma, S. Špacapan, A forbidden subgraph characterization of some graph classes using betweenness axioms, Discrete Math. 313 (2013), 951-958. https://doi.org/10.1016/j.disc.2013.01.013
- M. Changat, J. Mathew, H.M. Mulder, Discrete Appl. Math. The induced path function, monotonicity and betweenness, Discrete Appl. Math. 158 (2010), no. 5, 426-433. https://doi.org/10.1016/j.dam.2009.10.004
- M. Changat, L.K. Sheela, P.G. Narasimha-Shenoi, The axiomatic characterization of the interval function of distance hereditary graphs, submitted.
- V. Chepoi, Some properties of \(d\)-convexity in triangulated graphs, Math. Res. 87 (1986), 164-177 [in Russian].
- V. Chvátal, D. Rautenbach, P.M. Schäfer, Finite Sholander trees, trees, and their betweenness, Discrete Math. 311 (2011), 2143-2147. https://doi.org/10.1016/j.disc.2011.06.011
- H.N. de Ridder et al., Information System on Graph Classes and their Inclusions, (ISGCI).
- E. Howorka, A characterization of ptolemaic graphs, A characterization of Ptolemaic graphs, J. Graph Theory 5 (1981), 323-331. https://doi.org/10.1002/jgt.3190050314
- D. Kay, G. Chartrand, A characterization of certain Ptolemaic graphs, Canad. J. Math. 17 (1965), 342-346. https://doi.org/10.4153/CJM-1965-034-0
- H.M. Mulder, The Interval Function of a Graph, MC Tract 132, Amsterdam, 1980.
- H.M. Mulder, Transit functions on graphs (and posets), Proc. Int. Conf. - Convexity in Discrete Structures 5 (2008), 117-130.
- H.M. Mulder, L. Nebeský, Axiomatic characterization of the interval function of a graph, European J. Combin 30 (2009), 1172-1185. https://doi.org/10.1016/j.ejc.2008.09.007
- L. Nebeský, A characterization of the interval function of a connected graph, Czechoslovak Math. J. 44 (1994), 173-178.
- L. Nebeský, A characterization of the set of all shortest paths in a connected graph, Math. Bohem. 119 (1994), no. 1, 15-20.
- L. Nebeský, A characterization of geodetic graphs, Czechoslovak Math. J. 45 45 (1995), no. 3, 491-493.
- L. Nebeský, Characterizing the interval function of a connected graph, Math. Bohem. 123 (1998), no. 2, 137-144.
- 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.
- L. Nebeský, Characterization of the interval function of a (finite or infinite) connected graph, Czechoslovak Math. J. 51 (2001), 635-642.
- L. Nebeský, The induced paths in a connected graph and a ternary relation determined by them, Math. Bohem. 127 (2002), 397-408.
- M. Sholander, Trees, lattices, order, and betweenness, Proc. Amer. Math. Soc. 3 (1952), 369-381.
- Manoj Changat
- Department of Futures Studies, University of Kerala, Trivandrum, India - 695 581
- Lekshmi Kamal K. Sheela
- Department of Futures Studies, University of Kerala, Trivandrum, India - 695 581
- Prasanth G. Narasimha-Shenoi (corresponding author)
- Department of Mathematics, Government College Chittur, Palakkad, India - 678 104
- Communicated by Andrzej Żak.
- Received: 2022-06-08.
- Revised: 2023-02-27.
- Accepted: 2023-03-02.
- Published online: 2023-05-17.
