Not every graph can be reconstructed from its boundary distance matrix

Cáceres, José; Pelayo, Ignacio M

doi:10.22049/cco.2026.30664.2580

تعداد نشریات	6
تعداد شماره‌ها	125
تعداد مقالات	1,584
تعداد مشاهده مقاله	1,746,095
تعداد دریافت فایل اصل مقاله	1,623,194

	Not every graph can be reconstructed from its boundary distance matrix
Communications in Combinatorics and Optimization
مقالات آماده انتشار، پذیرفته شده، انتشار آنلاین از تاریخ 06 اردیبهشت 1405 اصل مقاله (728.18 K)
نوع مقاله: Original paper
شناسه دیجیتال (DOI): 10.22049/cco.2026.30664.2580
نویسندگان
José Cáceres^* ¹؛ Ignacio M Pelayo²
¹CDTIME and Departamento de Matemáticas, Universidad de Almería, Almería, Spain
²Departament de Matemàtiques, Universitat Politècnica de Catalunya, Barcelona, Spain
چکیده
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$.
کلیدواژه‌ها
Boundary؛ Distance Matrix؛ Ptolemaic graphs؛ Interval graphs

مراجع
[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.
آمار تعداد مشاهده مقاله: 85 تعداد دریافت فایل اصل مقاله: 56

سامانه مدیریت نشریات علمی. قدرت گرفته از سیناوب

پیوندهای مفید

آمار

Not every graph can be reconstructed from its boundary distance matrix