1. bookAHEAD OF PRINT
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

A Characterization of Uniquely Representable Graphs

Published Online: 08 Jul 2021
Volume & Issue: AHEAD OF PRINT
Page range: -
Received: 14 Jul 2020
Accepted: 24 May 2021
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
Abstract

The betweenness structure of a finite metric space M =(X, d) is a pair ℬ(M)=(X, βM) where βM is the so-called betweenness relation of M that consists of point triplets (x, y, z) such that d(x, z)= d(x, y)+ d(y, z). The underlying graph of a betweenness structure ℬ=(X, β)isthe simple graph G(ℬ)=(X, E) where the edges are pairs of distinct points with no third point between them. A connected graph G is uniquely representable if there exists a unique metric betweenness structure with underlying graph G. It was implied by previous works that trees are uniquely representable. In this paper, we give a characterization of uniquely representable graphs by showing that they are exactly the block graphs. Further, we prove that two related classes of graphs coincide with the class of block graphs and the class of distance-hereditary graphs, respectively. We show that our results hold not only for metric but also for almost-metric betweenness structures.

Keywords

MSC 2010

[1] P. Aboulker, X. Chen, G. Huzhang, R. Kapadia and C. Supko, Lines, betweenness and metric spaces, Discrete Comput. Geom. 56 (2016) 427–448.10.1007/s00454-016-9806-2Search in Google Scholar

[2] P. Aboulker and R. Kapadia, The Chen-Chvátal conjecture for metric spaces induced by distance-hereditary graphs, European J. Combin. 43 (2015) 1–7. https://doi.org/10.1016/j.ejc.2014.06.00910.1016/j.ejc.2014.06.009Search in Google Scholar

[3] P. Aboulker, M. Matamala, P. Rochet and J. Zamora, A new class of graphs that satisfies the Chen-Chvátal conjecture, J. Graph Theory 87 (2018) 77–88. https://doi.org/10.1002/jgt.2214210.1002/jgt.22142Search in Google Scholar

[4] 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) 885–894. https://doi.org/10.1016/j.disc.2015.01.00410.1016/j.disc.2015.01.004Search in Google Scholar

[5] H.-J. Bandelt and A.W.M. Dress, A canonical decomposition theory for metrics on a finite set,Adv.Math. 92 (1992) 47–105. https://doi.org/10.1016/0001-8708(92)90061-O10.1016/0001-8708(92)90061-OSearch in Google Scholar

[6] H.-J. Bandelt and H.M. Mulder, Distance-hereditary graphs,J. Combin. Theory Ser. B 41 (1986) 182–208. https://doi.org/10.1016/0095-8956(86)90043-210.1016/0095-8956(86)90043-2Search in Google Scholar

[7] L. Beaudou, A. Bondy, X. Chen, E. Chiniforooshan, M. Chudnovsky, V. Chvátal, N. Fraiman and Y. Zwols, A de Bruijn-Erd˝os theorem for chordal graphs, Electron. J. Combin. 22 (2015) #P1.70. https://doi.org/10.37236/352710.37236/3527Search in Google Scholar

[8] L. Beaudou, G. Kahn and M. Rosenfeld, Bisplit graphs satisfy the Chen-Chvátal conjecture, Discrete Math. Theor. Comput. Sci. 21 (2019) #5.Search in Google Scholar

[9] B. Brešar, M. Changat, J. Mathews, I. Peterin, P.G. Narasimha-Shenoi and A.T. Horvat, Steiner intervals, geodesic intervals, and betweenness, Discrete Math. 309 (2009) 6114–6125. https://doi.org/10.1016/j.disc.2009.05.02210.1016/j.disc.2009.05.022Search in Google Scholar

[10] P. Buneman, A note on the metric properties of trees,J. Combin. TheorySer.B 17 (1974) 48–50. https://doi.org/10.1016/0095-8956(74)90047-110.1016/0095-8956(74)90047-1Search in Google Scholar

[11] L. Burigana, Tree representation of qualitive proximities, Math. Social Sci. 185 (2009) 5–36. https://doi.org/10.4000/msh.1100010.4000/msh.11000Search in Google Scholar

[12] M. Changat, S. Klavžar and H.M. Mulder, The all-paths transit function of a graph, Czechoslovak Math. J. 51 (2001) 439–448. https://doi.org/10.1023/A:101371551844810.1023/A:1013715518448Search in Google Scholar

[13] M. Changat, A.K. Lakshmikuttyamma, J. Mathews, I. Peterin, P.G. Narasimha-Shenoi, G. Seethakuttyamma and 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.01310.1016/j.disc.2013.01.013Search in Google Scholar

[14] M. Changat and J. Mathew, Induced path transit function, monotone and Peano axioms, Discrete Math. 286 (2004) 185–194. https://doi.org/10.1016/j.disc.2004.02.01710.1016/j.disc.2004.02.017Search in Google Scholar

[15] M. Changat, J. Mathew and H.M. Mulder, Induced path transit function, betweenness and monotonicity, Electron. Notes Discrete Math. 15 (2003) 60–63. https://doi.org/10.1016/S1571-0653(04)00531-110.1016/S1571-0653(04)00531-1Search in Google Scholar

[16] M. Changat, J. Mathew and H.M. Mulder, The induced path function, monotonicity and betweenness, Discrete Appl. Math. 158 (2010) 426–433. https://doi.org/10.1016/j.dam.2009.10.00410.1016/j.dam.2009.10.004Search in Google Scholar

[17] M. Changat, P.G. Narasimha-Shenoi and G. Seethakuttyamma, Betweenness in graphs: A short survey on shortest and induced path betweenness,AKCE Int. J. Graphs Comb. 16 (2019) 96–109. https://doi.org/10.1016/j.akcej.2018.06.00710.1016/j.akcej.2018.06.007Search in Google Scholar

[18] M. Changat, F.H. Nezhad and N. Narayanan, Axiomatic characterization of the interval function of a bipartite graph, in: Algorithms Discrete Appl. Math., D. Gaur and N.S. Narayareswany (Ed(s)) (2018) 96–106. https://doi.org/10.1007/978-3-319-53007-9 910.1007/978-3-319-53007-9Search in Google Scholar

[19] M. Changat, I. Peterin, A. Ramachandran and A. Tepeh, The induced path transit function and the Pasch axiom, Bull. Malays. Math. Sci. Soc. (2) 39 (2016) 123–134. https://doi.org/10.1007/s40840-015-0285-z10.1007/s40840-015-0285-zSearch in Google Scholar

[20] X. Chen, The Sylvester-Chvátal theorem, Discrete Comput. Geom. 35 (2006) 193–199. https://doi.org/10.1007/s00454-005-1216-910.1007/s00454-005-1216-9Search in Google Scholar

[21] X. Chen and V. Chvátal, Problems related to a de Bruijn-Erd˝os theorem, Discrete Appl. Math. 156 (2008) 2101–2108. https://doi.org/10.1016/j.dam.2007.05.03610.1016/j.dam.2007.05.036Search in Google Scholar

[22] V. Chvátal, A de Bruijn-Erd˝os theorem for 12 metric spaces, Czechoslovak Math. J. 64 (2014) 45–51. https://doi.org/10.1007/s10587-014-0081-110.1007/s10587-014-0081-1Search in Google Scholar

[23] V. Chvátal, Sylvester-Gallai theorem and metric betweenness, Discrete Comput. Geom. 31 (2004) 175–195. https://doi.org/10.1007/s00454-003-0795-610.1007/s00454-003-0795-6Search in Google Scholar

[24] A. Dress, The Category of X-Nets, in: Networks: From Biology to Theory, J. Feng, J. Jost, M. Qian (Ed(s)), (Springer London, 2007) 3–22. https://doi.org/10.1007/978-1-84628-780-0_110.1007/978-1-84628-780-0_1Search in Google Scholar

[25] A. Dress, K.T. Huber, J. Koolen, V. Moulton and A. Spillner, Characterizing block graphs in terms of their vertex-induced partitions,Australas.J.Combin. 66 (2016) 1–9.Search in Google Scholar

[26] A. Dress and M. Krüger, Parsimonious phylogenetic trees in metric spaces and simulated annealing, Adv. in Appl. Math. 8 (1987) 8–37. https://doi.org/10.1016/0196-8858(87)90003-010.1016/0196-8858(87)90003-0Search in Google Scholar

[27] F. Harary, A characterization of block-graphs, Canad. Math. Bull. 6 (1963) 1–6. https://doi.org/10.4153/CMB-1963-001-x10.4153/CMB-1963-001-xSearch in Google Scholar

[28] E. Howorka, On metric properties of certain clique graphs,J.Combin. Theory Ser. B 27 (1979) 67–74. https://doi.org/10.1016/0095-8956(79)90069-810.1016/0095-8956(79)90069-8Search in Google Scholar

[29] E. Howorka, A characterization of distance-hereditary graphs, Q. J. Math 28 (1977) 417–420. https://doi.org/10.1093/qmath/28.4.41710.1093/qmath/28.4.417Search in Google Scholar

[30] J.R. Isbell, Six theorems about injective metric spaces,Comment. Math. Helv. 39 (1964) 65–76. https://doi.org/10.1007/BF0256694410.1007/BF02566944Search in Google Scholar

[31] I. Kantor and B. Patkós, Towards a de Bruijn-Erd˝os theorem in the L1-metric, Discrete Comput. Geom. 49 (2013) 659–670. https://doi.org/10.1007/s00454-013-9496-y10.1007/s00454-013-9496-ySearch in Google Scholar

[32] D.C. Kay and G. Chartrand, A characterization of certain ptolemaic graphs, Canad. J. Math. 17 (1965) 342–346. https://doi.org/10.4153/CJM-1965-034-010.4153/CJM-1965-034-0Search in Google Scholar

[33] V.B. Le and N.N. Tuy, The square of a block graph, Discrete Math. 310 (2010) 734–741. https://doi.org/10.1016/j.disc.2009.09.00410.1016/j.disc.2009.09.004Search in Google Scholar

[34] M.A. Morgana and H.M. Mulder, The induced path convexity, betweenness, and svelte graphs, Discrete Math. 254 (2002) 349–370. https://doi.org/10.1016/S0012-365X(01)00296-510.1016/S0012-365X(01)00296-5Search in Google Scholar

[35] H.M. Mulder, The interval function of a graph (Mathematical Centre Tracts 132, Mathematisch Centrum,Amsterdam, 1980). https://doi.org/10.21136/CMJ.1994.12844910.21136/CMJ.1994.128449Search in Google Scholar

[36] H.M. Mulder and 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.00710.1016/j.ejc.2008.09.007Search in Google Scholar

[37] H.M. Mulder, Transit functions on graphs (and posets), in: Convexity in Discrete Structures, M. Changat, S. Klavžar, H.M. Mulder and A. Vijayakumar (Ed(s)), (Ramanujan Math. Soc. Lect. Notes Ser. 5, 2008) 117–130.Search in Google Scholar

[38] L. Nebeský, A characterization of the interval function of a connected graph, Czechoslovak Math. J. 44 (1994) 173–178. https://doi.org/10.21136/CMJ.1994.12844910.21136/CMJ.1994.128449Search in Google Scholar

[39] L. Nebeský, A characterization of the set of all shortest paths in a connected graph, Math. Bohem. 119 (1994) 15–20. https://doi.org/10.21136/MB.1994.12620810.21136/MB.1994.126208Search in Google Scholar

[40] L. Nebeský, Characterizing the interval function of a connected graph, Math. Bohem. 123 (1998) 137–144. https://doi.org/10.21136/MB.1998.12630710.21136/MB.1998.126307Search in Google Scholar

[41] L. Nebeský, A characterization of the interval function of a (finite or infinite) connected graph, Czechoslovak Math. J. 51 (2001) 635–642. https://doi.org/10.1023/A:101374432480810.1023/A:1013744324808Search in Google Scholar

[42] L. Nebeský, The interval function of a connected graph and a characterization of geodetic graphs, Math. Bohem. 126 (2001) 247–254. https://doi.org/10.21136/MB.2001.13390910.21136/MB.2001.133909Search in Google Scholar

[43] L. Nebeský, The induced paths in a connected graph and a ternary relation determined by them, Math. Bohem. 127 (2002) 397–408. https://doi.org/10.21136/MB.2002.13407210.21136/MB.2002.134072Search in Google Scholar

[44] R. Schrader and L. Stenmans, A de Bruijn-Erdös theorem for (q, q − 4)-graphs, Discrete Appl. Math. 279 (2019) 198–201. https://doi.org/10.1016/j.dam.2019.11.00810.1016/j.dam.2019.11.008Search in Google Scholar

[45] M. Sholander, Trees, lattices, order, and betweenness,Proc. Amer. Math. Soc. 3 (1952) 369–381. https://doi.org/10.1090/S0002-9939-1952-0048405-510.1090/S0002-9939-1952-0048405-5Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo