Hierarchy of Subfamilies of Ptolemaic Graphs: Axiomatic Characterizations and Interval Functions

Articles in Press

Document Type : Original paper

Authors

1 Department of Mathematics, University of Kerala, Thiruvananthapuram, Kerala, India

2 Department of Futures Studies, University of Kerala, Thiruvananthapuram, Kerala, India

Abstract

Ptolemaic graphs are precisely the graphs that are both chordal and distance-hereditary. Markenzon et al.~\cite{markenzon} established a hierarchy of Ptolemaic graphs comprising six subfamilies: laminar chordal graphs, block duplicate graphs, block graphs, AC graphs, trees, and paths. In this paper, we present a new proof of the characterization of AC graphs using forbidden induced subgraphs and identify an additional graph class that lies between AC graphs and paths within this hierarchy.



The interval function is a well-studied tool in metric graph theory, and the characterization of the interval function of graph families is an interesting problem in metric graph theory having connections to first-order logic. In this paper, we propose a set of independent betweenness axioms for an arbitrary function known as a transit function and provide a characterization of the interval functions corresponding to graphs in the extended hierarchy of subgraphs of Ptolemaic graphs, specifically laminar chordal graphs, block duplicate graphs, and AC graphs.

Keywords

Main Subjects

References

[1] A. Anil and M. Changat, Ptolemaic and chordal cover-incomparability graphs, Order 39 (2022), no. 1, 29–43. https://doi.org/10.1007/s11083-021-09551-w
[2] K. Balakrishnan, M. Changat, A.K. Lakshmikuttyamma, J. Mathew, H.M. Mulder, P.G. Narasimha-Shenoi, and N. Narayanan, Axiomatic characterization of the interval function of a block graph, Discrete Math. 338 (2015), no. 6, 885–894.
https://doi.org/10.1016/j.disc.2015.01.004
[3] H.J. Bandelt and H.M. Mulder, Distance-hereditary graphs, J. Combin. Theory Ser. B 41 (1986), no. 2, 182–208.
https://doi.org/10.1016/0095-8956(86)90043-2
[4] J.R.S. Blair, The efficiency of ac graphs, Discrete Appl. Math. 44 (1993), no. 1-3, 119–138. https://doi.org/10.1016/0166-218X(93)90227-F
[5] J.R.S. Blair and S.S. Ravi, Proceedings twenty-seventh conference on communication, ch. TR-matching for chordal graphs, pp. 72–81, Control, and Computing, 1989.
[6] B. Brešar, M. Changat, S. Klavžar, M. Kovše, J. Mathews, and A. Mathews, Cover-incomparability graphs of posets, Order 25 (2008), no. 4, 335–347.  https://doi.org/10.1007/s11083-008-9097-1
[7] J. Chalopin, M. Changat, V. Chepoi, and J. Jacob, First-order logic axiomatization of metric graph theory, Theoret. Comput. Sci. 993 (2024), 114460.  https://doi.org/10.1016/j.tcs.2024.114460
[8] M. Changat, A.K. Lakshmikuttyamma, J. Mathews, I. Peterin, P.G. Narasimha-Shenoi, G. Seethakuttyamma, and S. ˇSpacapan, A forbidden subgraph characterization of some graph classes using betweenness axioms, Discrete Math. 313
(2013), no. 8, 951–958.  https://doi.org/10.1016/j.disc.2013.01.013
[9] M. Changat, J. Mathew, and H.M. Mulder, 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
[10] M. Changat, L.K.K. Sheela, and P.G. Narasimha-Shenoi, Axiomatic characterizations of ptolemaic and chordal graphs, Opuscula Math. 43 (2023), no. 3, 393–407.  http://dx.doi.org/10.7494/OpMath.2023.43.3.393
[11] V. Chvátal, D. Rautenbach, and P.M. Schäfer, Finite sholander trees, trees, and their betweenness, Discrete Math. 311 (2011), no. 20, 2143–2147.  https://doi.org/10.1016/j.disc.2011.06.011
[12] M.C. Golumbic and U.N. Peled, Block duplicate graphs and a hierarchy of chordal graphs, Discrete Appl. Math. 124 (2002), no. 1-3, 67–71. https://doi.org/10.1016/S0166-218X(01)00330-4
[13] M. Habib and J. Stacho, Reduced clique graphs of chordal graphs, European J. Combin. 33 (2012), no. 5, 712–735.
https://doi.org/10.1016/j.ejc.2011.09.031
[14] E. Howorka, A characterization of ptolemaic graphs, J. Graph Theory 5 (1981), no. 3, 323–331. https://doi.org/10.1002/jgt.3190050314
[15] W. Kennedy, Strictly chordal graphs and phylogenetic roots, Master’s thesis, University of Alberta, 2005.
[16] W. Kennedy, G. Lin, and G. Yan, Strictly chordal graphs are leaf powers, J. Discrete Algorithms 4 (2006), no. 4, 511–525.
https://doi.org/10.1016/j.jda.2005.06.005
[17] L. Markenzon and P.R. da Costa Pereira, One-phase algorithm for the determination of minimal vertex separators of chordal graphs, Int. Trans. Oper. Res. 17 (2010), no. 6, 683–690.  https://doi.org/10.1111/j.1475-3995.2009.00751.x
[18] L. Markenzon and C.F.E.M. Waga, New results on ptolemaic graphs, Discrete Appl. Math. 196 (2015), 135–140.
https://doi.org/10.1016/j.dam.2014.03.024
[19] M.A. Morgana and H.M. Mulder, The induced path convexity, betweenness, and svelte graphs, Discrete Math. 254 (2002), no. 1-3, 349–370.  https://doi.org/10.1016/S0012-365X(01)00296-5
[20] H.M. Mulder and L. L. Nebeský, Axiomatic characterization of the interval function of a graph, European J. Combin. 30 (2009), no. 5, 1172–1185.  https://doi.org/10.1016/j.ejc.2008.09.007
[21] H.M. Mulder, The Interval Function of a Graph, Mathematisch Centrum, 1980.
[22] H.M. Mulder, Lecture Notes Series, Ramanujan Math. Soc., Mysore, 2008, pp. 117–130.
[23] H.M. Mulder and A. Schrijver, Median graphs and helly hypergraphs, Discrete Math. 25 (1979), no. 1, 41–50. https://doi.org/10.1016/0012-365X(79)90151-1
[24] L. Nebeský, A characterization of the interval function of a connected graph, Czechoslovak Math. J. 44 (1994), no. 1, 173–178.
[25] L. Nebeský, Characterizing the interval function of a connected graph, Math. Bohem. 123 (1998), no. 2, 137–144.
http://dx.doi.org/10.21136/MB.1998.126307
[26] L. Nebeský, A characterization of the interval function of a (finite or infinite) connected graph, Czechoslovak Math. J. 51 (2001), no. 3, 635–642.  https://doi.org/10.1023/A:1013744324808
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 14 May 2025

Files

Share

How to cite

Statistics