REAL

A Characterization of Uniquely Representable Graphs

Szabó, Péter G.N. (2021) A Characterization of Uniquely Representable Graphs. DISCUSSIONES MATHEMATICAE GRAPH THEORY. ISSN 1234-3099

[img]
Preview
Text
1708.01272.pdf

Download (487kB) | Preview

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. © 2021 Péter G.N. Szabó.

Item Type: Article
Uncontrolled Keywords: graph representation; Block graph; distance-hereditary graph; finite metric space; metric betweenness;
Subjects: Q Science / természettudomány > QA Mathematics / matematika
SWORD Depositor: MTMT SWORD
Depositing User: MTMT SWORD
Date Deposited: 18 Jan 2023 15:11
Last Modified: 18 Jan 2023 15:11
URI: http://real.mtak.hu/id/eprint/156806

Actions (login required)

Edit Item Edit Item