آمار
| تعداد نشریات | 6 |
| تعداد شمارهها | 122 |
| تعداد مقالات | 1,551 |
| تعداد مشاهده مقاله | 1,649,917 |
| تعداد دریافت فایل اصل مقاله | 1,543,823 |
Hierarchy of Subfamilies of Ptolemaic Graphs: Axiomatic Characterizations and Interval Functions | ||
| Communications in Combinatorics and Optimization | ||
| مقالات آماده انتشار، پذیرفته شده، انتشار آنلاین از تاریخ 24 اردیبهشت 1404 اصل مقاله (602.71 K) | ||
| نوع مقاله: Original paper | ||
| شناسه دیجیتال (DOI): 10.22049/cco.2025.30144.2335 | ||
| نویسندگان | ||
| Abdultamim Ahadi1؛ Arun Anil2؛ Manoj Changat* 2 | ||
| 1Department of Mathematics, University of Kerala, Thiruvananthapuram, Kerala, India | ||
| 2Department of Futures Studies, University of Kerala, Thiruvananthapuram, Kerala, India | ||
| چکیده | ||
| 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. | ||
| کلیدواژهها | ||
| Ptolemaic graph؛ laminar chordal؛ AC graph؛ transit function؛ interval function | ||
| مراجع | ||
|
[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 | ||
|
آمار تعداد مشاهده مقاله: 327 تعداد دریافت فایل اصل مقاله: 190 |
||