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.

Full text (pdf)

  1. 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
  2. A. Brandstädt, V.B. Le, J.P. Spinrad, Graph Classes - A Survey, SIAM Monogr. J. Discrete Math., 1999.
  3. 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.
  4. 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.
  5. 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.
  6. 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
  7. 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
  8. M. Changat, L.K. Sheela, P.G. Narasimha-Shenoi, The axiomatic characterization of the interval function of distance hereditary graphs, submitted.
  9. V. Chepoi, Some properties of \(d\)-convexity in triangulated graphs, Math. Res. 87 (1986), 164-177 [in Russian].
  10. 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
  11. H.N. de Ridder et al., Information System on Graph Classes and their Inclusions, (ISGCI).
  12. 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
  13. 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
  14. H.M. Mulder, The Interval Function of a Graph, MC Tract 132, Amsterdam, 1980.
  15. H.M. Mulder, Transit functions on graphs (and posets), Proc. Int. Conf. - Convexity in Discrete Structures 5 (2008), 117-130.
  16. 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
  17. L. Nebeský, A characterization of the interval function of a connected graph, Czechoslovak Math. J. 44 (1994), 173-178.
  18. L. Nebeský, A characterization of the set of all shortest paths in a connected graph, Math. Bohem. 119 (1994), no. 1, 15-20.
  19. L. Nebeský, A characterization of geodetic graphs, Czechoslovak Math. J. 45 45 (1995), no. 3, 491-493.
  20. L. Nebeský, Characterizing the interval function of a connected graph, Math. Bohem. 123 (1998), no. 2, 137-144.
  21. 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.
  22. L. Nebeský, Characterization of the interval function of a (finite or infinite) connected graph, Czechoslovak Math. J. 51 (2001), 635-642.
  23. L. Nebeský, The induced paths in a connected graph and a ternary relation determined by them, Math. Bohem. 127 (2002), 397-408.
  24. 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.
Opuscula Mathematica - cover

Cite this article as:
Manoj Changat, Lekshmi Kamal K. Sheela, Prasanth G. Narasimha-Shenoi, Axiomatic characterizations of Ptolemaic and chordal graphs, Opuscula Math. 43, no. 3 (2023), 393-407, https://doi.org/10.7494/OpMath.2023.43.3.393

Download this article's citation as:
a .bib file (BibTeX),
a .ris file (RefMan),
a .enw file (EndNote)
or export to RefWorks.

We advise you this website uses cookies to allow us to see how the site is used. All data is anonymized.
All recent versions of popular browsers give users a level of control over cookies. Users can set their browsers to accept or reject all, or certain, cookies.