A characterization of uniquely representable graphs

Szabó, Péter G. N.  

Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 4, pp. 999-1017

Résumé

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,β) is the 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.

Détail

Keywords: finite metric space, metric betweenness, block graph, distance-hereditary graph, graph representation

Bibliographie

[1] P. Aboulker, X. Chen, G. Huzhang, R. Kapadia and C. Supko, Lines, betweenness and metric spaces, Discrete Comput. Geom. 56 (2016) 427–448. https://doi.org/10.1007/s00454-016-9806-2

[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.009

[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.22142

[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.004

[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-O

[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-2

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

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

[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.022

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

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

[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:1013715518448

[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.013

[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.017

[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-1

[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.004

[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.007

[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_9

[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-z

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

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

[22] V. Chvátal, A de Bruijn-Erdős theorem for 1–2 metric spaces, Czechoslovak Math. J. 64 (2014) 45–51. https://doi.org/10.1007/s10587-014-0081-1

[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-6

[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_1

[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.

[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-0

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

[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-8

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

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

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

[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-0

[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.004

[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-5

[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.128449

[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.007

[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.

[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.128449

[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.126208

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

[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:1013744324808

[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.133909

[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.134072

[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.008

[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-5