Geodesic
A characterization of uniquely representable graphs
Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 4, pp. 999-1017

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: finite metric space, metric betweenness, block graph, distance-hereditary graph, graph representation 
@article{DMGT_2023_43_4_a7,
     author = {Szab\'o, P\'eter G. N.},
     title = {A characterization of uniquely representable graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {999--1017},
     publisher = {mathdoc},
     volume = {43},
     number = {4},
     year = {2023},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2023_43_4_a7/}
}
TY  - JOUR
AU  - Szabó, Péter G. N.
TI  - A characterization of uniquely representable graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2023
SP  - 999
EP  - 1017
VL  - 43
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2023_43_4_a7/
LA  - en
ID  - DMGT_2023_43_4_a7
ER  - 
%0 Journal Article
%A Szabó, Péter G. N.
%T A characterization of uniquely representable graphs
%J Discussiones Mathematicae. Graph Theory
%D 2023
%P 999-1017
%V 43
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2023_43_4_a7/
%G en
%F DMGT_2023_43_4_a7
Szabó, Péter G. N. A characterization of uniquely representable graphs. Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 4, pp. 999-1017. http://geodesic.mathdoc.fr/item/DMGT_2023_43_4_a7/