Not every graph can be reconstructed from its boundary distance matrix
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909634919399424 |
|---|---|
| author | Cáceres, José Pelayo, Ignacio M. |
| author_facet | Cáceres, José Pelayo, Ignacio M. |
| contents | 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 $κ$, being $κ$ the order of $\partial(G)$, such that for every $i,j\in \partial(G)$, $[\hat{D}_G]_{ij}=d_G(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 $\hat{D}_{G}$ 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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_02652 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Not every graph can be reconstructed from its boundary distance matrix Cáceres, José Pelayo, Ignacio M. Combinatorics 05C50, 15A18, 05C69 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 $κ$, being $κ$ the order of $\partial(G)$, such that for every $i,j\in \partial(G)$, $[\hat{D}_G]_{ij}=d_G(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 $\hat{D}_{G}$ 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$. |
| title | Not every graph can be reconstructed from its boundary distance matrix |
| topic | Combinatorics 05C50, 15A18, 05C69 |
| url | https://arxiv.org/abs/2506.02652 |