Axiomatic characterizations of Ptolemaic and chordal graphs

• Autorzy: Changat Manoj , Sheela Lekshmi Kamal K. , Narasimha-Shenoi Prasanth G.

Identyfikatory

DOI

10.7494/OpMath.2023.43.3.393

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

interval function; betweenness axioms; Ptolemaic graphs; transit function; induced path transit function

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2023
• Tom: Vol. 43, no. 3
• Strony: 393--407
• Opis fizyczny: Bibliogr. 24 poz., rys.

Twórcy

autor

Changat Manoj

• Department of Futures Studies, University of Kerala, Trivandrum, India - 695 581

autor

Sheela Lekshmi Kamal K.

• Department of Futures Studies, University of Kerala, Trivandrum, India - 695 581

autor

Narasimha-Shenoi Prasanth G.

• Department of Mathematics, Government College Chittur, Palakkad, India - 678 104

Bibliografia

• [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, Discrete Math. 338 (2015), 885–894.
• [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.
• [7] M. Changat, J. Mathew, H.M. Mulder, The induced path function, monotonicity and betweenness, Discrete Appl. Math. 158 (2010), no. 5, 426–433.
• [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.
• [11] H.N. de Ridder et al., Information System on Graph Classes and their Inclusions, (ISGCI), https://www.graphclasses.org.
• [12] E. Howorka, A characterization of Ptolemaic graphs, J. Graph Theory 5 (1981), 323–331.
• [13] D. Kay, G. Chartrand, A characterization of certain Ptolemaic graphs, Canad. J. Math. 17 (1965), 342–346.
• [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.
• [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 (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.

Uwagi

Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2022-2023)