Not every graph can be reconstructed from its boundary distance matrix

Articles in Press

Document Type : Original paper

Authors

1 CDTIME and Departamento de Matemáticas, Universidad de Almería, Almería, Spain

2 Departament de Matemàtiques, Universitat Politècnica de Catalunya, Barcelona, Spain

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 $\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)$. 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 $|\partial(G)|$ (and thus also the boundary distance matrix) of $G$ are prefixed (i.e., the set of boundary vertices is known as a subset of $V$, but not their identities). 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$.   

Keywords

Main Subjects

References

[1] M. Ahmed and C. Wenk, Constructing street networks from GPS trajectories, Lecture Notes in Computer Science, vol. 7501, ESA, 2012, pp. 60–71. https://doi.org/10.1007/978-3-642-33090-2_7
[2] H.J. Bandelt and H.M. Mulder, Distance-hereditary graphs, J. Combin. Theory Ser. B 41 (1986), no. 2, 182–208. https://doi.org/10.1016/0095-8956(86)90043-2
[3] U. Brandes and S. Cornelsen, Phylogenetic graph models beyond trees, Discrete Appl. Math. 157 (2009), no. 10, 2361–2369. https://doi.org/10.1016/j.dam.2008.06.031
[4] J. C´aceres, C. Hernando, M. Mora, I.M. Pelayo, M.L. Puertas, and C. Seara, On geodetic sets formed by boundary vertices, Discrete Math. 306 (2019), no. 2, 188–198. https://doi.org/ 10.1016/j.disc.2005.12.012
[5] J. Cáceres and I.M. Pelayo, Metric locations in pseudotrees: A survey and new results, Mathematics 13 (2025), no. 4, 560. https://doi.org/10.3390/math13040560
[6] J. Cáceres and I.M. Pelayo, Reconstructing a graph from the distance matrix of its boundary, Discuss. Math. Graph Theory (2025), In press. https://doi.org/10.7151/dmgt.2567
[7] G. Chartrand, D. Erwin, G.L. Johns, and P. Zhang, Boundary vertices in graphs, Discrete Math. 263 (2003), no. 1-3, 25–34. https://doi.org/10.1016/S0012-365X(02)00567-8.
[8] G. Chartrand, L. Lesniak, and P. Zhang, Graphs and Digraphs, CRC Press, Boca Raton, FL, 2024.
[9] T.K. Day, J. Wang, and Y. Wang, Graph reconstruction by discrete morse theory, Proceedings of the 34th International Symposium on Computational Geometry, vol. 99, 2018, pp. Art. No. 31,15. https://doi.org/10.4230/LIPIcs.SoCG.2018.31
[10] Gross O.A. Fulkerson, D.R., Incidence matrices and interval graphs, Pacific J. Math. 15 (1965), no. 3, 835–855.
[11] Prins G. Harary, F., The block-cutpoint tree of a graph, Publi. Math. Debrecen 13 (1966), no. (1-4), 103–107.
[12] C. Hernando, M. Mora, I.M. Pelayo, and C. Seara, Some structural, metric and convex properties of the boundary of a graph, Ars Combin. 109 (2013), 267–283. https://doi.org/10.1016/j.endm.2006.06.036
[13] S. Kannan, C. Mathieu, and H. Zhou, Graph reconstruction and verification, ACM Trans. Algorithms 14 (2018), no. 4, 1–30. https://doi.org/10.1145/3199606
[14] P.J. Kelly, On isometric transformations, Ph.D. thesis, University of Wisconsin, 1942.
[15] D. Kuziak, The strong resolving graph and the strong metric dimension of cactus graphs, Mathematics 8 (2020), no. 8, 1266. https://doi.org/10.3390/math8081266
[16] B. McKay, (n.d.). Combinatorial Data. Retrieved May 28, 2025, from https://users.cecs.anu.edu.au/ bdm/data/
[17] E. Mossel and N. Ross, Shotgun assembly of labeled graphs, IEEE Trans. Network Sci. Eng., vol. 6, 2019, pp. 145–157.
https://doi.org/10.1109/TNSE.2017.2776913
[18] O.R. Oellermann and J. Peters-Fransen, The strong metric dimension of graphs and digraphs, Discrete Appl. Math. 155 (2007), no. 3, 356–364. https://doi.org/10.1016/j.dam.2006.06.009
[19] J.A. Rodríguez-Velázquez, I.G. Yero, D. Kuziak, and O.R. Oellermann, On the strong metric dimension of Cartesian and direct products of graphs, Discrete Math. 335 (2014), 8–19. https://doi.org/10.1016/j.disc.2014.06.023
[20] A Sébo and E. Tannier, On metric generators of graphs, Math. Oper. Res. 29 (2004), no. 2, 383–393. https://doi.org/10.1287/moor.1030.0070
[21] Y.A. Smolenskii, A method for the linear recording of graphs, USSR Comput. Math. Math. Physics 2 (1962), no. 2, 396–397.
[22] S.M. Ulam, A Collection of Mathematical Problems, In: Interscience Tracts in Pure and Applied Mathematics 8, Interscience Publishers, 1960.
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 26 April 2026

Files

Share

How to cite

Statistics