آمار
| تعداد نشریات | 6 |
| تعداد شمارهها | 123 |
| تعداد مقالات | 1,577 |
| تعداد مشاهده مقاله | 1,706,896 |
| تعداد دریافت فایل اصل مقاله | 1,590,109 |
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* 1؛ Ignacio M Pelayo2 | ||
| 1CDTIME and Departamento de Matemáticas, Universidad de Almería, Almería, Spain | ||
| 2Departament 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. | ||
|
آمار تعداد مشاهده مقاله: 79 تعداد دریافت فایل اصل مقاله: 41 |
||