{
  "id": "2404.04039",
  "version": "v1",
  "published": "2024-04-05T11:49:28.000Z",
  "updated": "2024-04-05T11:49:28.000Z",
  "title": "Reconstructing a pseudotree from the distance matrix of its boundary",
  "authors": [
    "José Cáceres",
    "Ignacio M. Pelayo"
  ],
  "categories": [
    "math.CO"
  ],
  "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 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)$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2024-04-05T11:49:28.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C12",
      "05C85",
      "68R10"
    ],
    "keywords": [
      "distance matrix",
      "boundary vertex",
      "pseudotree",
      "unicyclic graph",
      "square matrix"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}