Reconstructing a pseudotree from the distance matrix of its boundary

José Cáceres, Ignacio M. Pelayo

Published 2024-04-05Version 1

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 distance matrix $\hat{D}_G$ of the boundary of a graph $G$ is the square matrix of order $\kappa$, being $\kappa$ 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 $\kappa$, 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 tree or a unicyclic graph with girth $g\geq 5$ vertices, then $G$ is uniquely determined by the distance matrix $\hat{D}_{G}$ of the boundary of $G$ and we also conjecture that this statement holds for every connected graph. Moreover, two algorithms for reconstructing a tree and a unicyclic graph from the distance matrix of their boundaries are given, whose time complexities in the worst case are, respectively, $O(\kappa n)$ and $O(n^2)$.