2025/06/03 by José Cáceres, Ignacio M. Pelayo, Cáceres, José +1
Computer Science · Mathematics · #05C50 #05C69 #15A18 #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Matrix Theory and Algorithms #Neural Networks and Applications
paper · pdf · doi:10.48550/arxiv.2506.02652
openalex publication_date 2025/06/03 · openalex created_date 2025/10/14 · openalex updated_date 2026/07/28
A vertex v of a connected graph G is said to be a boundary vertex of G if for some other vertex u of G, no neighbor of v is further away from u than v. The boundary ∂(G) of G is the set of all of its boundary vertices. The boundary distance matrix DG of a graph G=([n],E) is the square matrix of order κ, being κ the order of ∂(G), such that for every i,j∈ ∂(G), [DG]ij=dG(i,j). In a recent paper [doi.org/10.7151/dmgt.2567], it was shown that if a graph G is either a block graph or a unicyclic graph, then G is uniquely determined by the boundary distance matrix DG of G, and it was also conjectured that this statement holds for every connected graph G, whenever both the order n and the boundary (and thus also the boundary distance matrix) of G are prefixed. After proving that this conjecture is true for several graph families, such as being of diameter 2, having order at most n=6 or being Ptolemaic, we show that this statement does not hold when considering, for example, either the family of split graphs of diameter 3 and order at least n=10 or the family of distance-hereditary graphs of order at least n=8.