Reconstructing a graph from the distance matrix of its boundary

Abstract

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 $\partial (G)$ of $G$ is the set of all of its boundary vertices. The boundary distance matrix ${\hat{D}}_G$ of a graph $G=([n],E)$ is the square matrix of order $\hat{I}º$, being $\hat{I}º$ the order of $\partial (G)$, such that for every $i,j\in \partial (G)$, $[{\hat{D}}_G{]}_{ij}=d_G(i,j)$. Given a square matrix $\hat{B}$ of order $\hat{I}º$, we prove under which conditions $\hat{B}$ is the distance matrix ${\hat{D}}_T$ of the set of leaves of a tree $T$, which is precisely its boundary. We show that if $G$ is either a block graph or a unicyclic graph, then $G$ is uniquely determined by the boundary distance matrix ${\hat{D}}_G$ of $G$ and we also conjecture 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. Moreover, an algorithm for reconstructing a 1-block graph (resp., a unicyclic graph) from its boundary distance matrix is given, whose time complexity in the worst case is $O(\hat{I}ºn)$ (resp., $O(n^2)$).