DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

Discussiones Mathematicae Graph Theory

Article in volume

Authors:

P.G.N. Szabó

Péter G. N. Szabó

Budapest University of Technology and Economics, Department of Computer Science and Information Theory

email: szape@cs.bme.hu

0000-0001-8202-3721

Title:

A characterization of uniquely representable graphs

PDF

Source:

Discussiones Mathematicae Graph Theory 43(4) (2023) 999-1017

Received: 2020-07-14 , Revised: 2021-05-21 , Accepted: 2021-05-24 , Available online: 2021-06-19 , https://doi.org/10.7151/dmgt.2415

Abstract:

The betweenness structure of a finite metric space $M = (X, d)$ is a pair $\mathcal{B}(M)=(X,\beta_M)$ where $\beta_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 $\mathcal{B} = (X,\beta)$ is the simple graph $G(\mathcal{B}) = (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:

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

References:

  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 $L_1$-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
Close