Article in press
Authors:
Title:
Reconstructing a graph from the boundary distance matrix
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2024-05-17 , Revised: 2024-09-24 , Accepted: 2024-09-28 , Available online: 2024-10-23 , https://doi.org/10.7151/dmgt.2567
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$, with $\kappa$ being 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 block graph or a unicyclic graph, then $G$ is
uniquely determined by the boundary distance matrix $\hat{D}_{G}$ of $G$ and
we also conjecture 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.
Moreover, an algorithm for reconstructing a 1-block graph (respectively, a unicyclic
graph) from its boundary distance matrix is given, whose time complexity in the
worst case is $O(n)$ (respectively, $O(n^2)$).
Keywords:
boundary, distance matrix, block graph, unicyclic graph, realizability
References:
- M. Ahmed and C. Wenk, Constructing street networks from GPS trajectories, in: Algorithms-ESA 2012, L. Epstein and P. Ferragina (Ed(s)), Lecture Notes in Computer Science 7501, (Springer, Berlin, Heidelberg, 2012) 60–71.
https://doi.org/10.1007/978-3-642-33090-2_7 - U. Brandes and S. Cornelsen, Phylogenetic graph models beyond trees, Discrete Appl. Math. 157 (2009) 2361–2369.
https://doi.org/10.1016/j.dam.2008.06.031 - P. Buneman, A note on the metric properties of trees, J. Combin. Theory Ser. B 17 (1974) 48–50.
https://doi.org/10.1016/0095-8956(74)90047-1 - J. Cáceres, C. Hernando, M. Mora, I.M. Pelayo, M.L. Puertas and C. Seara, On geodetic sets formed by boundary vertices, Discrete Math. 306 (2006) 188–198.
https://doi.org/10.1016/j.disc.2005.12.012 - J. Cáceres, C. Hernando, M. Mora, I.M. Pelayo, M.L. Puertas, C. Seara and D.R. Wood, On the metric dimension of Cartesian products of graphs, SIAM J. Discrete Math. 21 (2007) 423–441.
https://doi.org/10.1137/050641867 - J. Cáceres and I.M. Pelayo, Metric locations in pseudotrees: A survey and new results (2023).
arXiv: 2307.13403v2 - G. Chartrand, D. Erwin, G.L. Johns and P. Zhang, Boundary vertices in graphs, Discrete Math. 263 (2003) 25–34.
https://doi.org/10.1016/S0012-365X(02)00567-8 - G. Chartrand, L. Lesniak and P. Zhang, Graphs and Digraphs, 6th Ed. (Chapman and Hall/CRC Press, 2016).
https://doi.org/10.1201/b19731 - T.K. Day, J. Wang and Y. Wang, Graph reconstruction by discrete Morse theory, in: Proc. 34th International Symposium on Computational Geometry, (Leibniz International Proceedings in Informatics (LIPIcs) 99 2018) 31:1–31:15.
https://doi.org/10.4230/LIPIcs.SoCG.2018.31 - R.L. Graham and H.O. Pollack, On the addressing problem for loop switching, Bell Syst. Tech. J. 50 (1971) 2495–2519.
- M. Gromov, Filling Riemannian manifolds, J. Differential Geom. 18 (1983) 1–147.
https://doi.org/10.4310/jdg/1214509283 - S.L. Hakimi and S.S. Yau, Distance matrix of a graph and its realizability, Quart. Appl. Math. 22 (1965) 305–317.
https://doi.org/10.1090/qam/184873 - Y. Hasegawa and A. Saito, Graphs with small boundary, Discrete Math. 307 (2007) 1801–1807.
https://doi.org/10.1016/j.disc.2006.09.028 - 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.
- E. Howorka, On metric properties of certain clique graphs, J. Combin. Theory Ser. B 27 (1979) 67–74.
https://doi.org/10.1016/0095-8956(79)90069-8 - S. Kannan, C. Mathieu and H. Zhou, Graph reconstruction and verification, ACM Trans. Algorithms 14(4) (2018) Article No. 40 1–30.
https://doi.org/10.1145/3199606 - P.J. Kelly, On Isometric Transformations, Ph.D. Thesis (University of Wisconsin, 1942).
- D. Kuziak, The strong resolving graph and the strong metric dimension of cactus graphs, Mathematics 2020 (8) 1266.
https://doi.org/10.3390/math8081266 - H. Lin, R. Liu and X. Lu, The inertia and energy of the distance matrix of a connected graph, Linear Algebra Appl. 467 (2015) 29–39.
https://doi.org/10.1016/j.laa.2014.10.045 - R. Michel, Sur la rigidité imposé par la longueur des géodésiques, Invent Math. 65 (1981/82) 71–84.
- E. Mossel and N. Ross, Shotgun assembly of labeled graphs, IEEE Trans. Network Sci. Eng. 6 (2019) 145–157.
https://doi.org/10.1109/TNSE.2017.2776913 - O.R. Oellermann and J. Peters-Fransen, The strong metric dimension of graphs and digraphs, Discrete Appl. Math. 155 (2007) 356–364.
https://doi.org/10.1016/j.dam.2006.06.009 - L. Pestov and G. Uhlmann, Two dimensional compact simple Riemannian manifolds are boundary distance rigid, Ann. of Math. 161 (2005) 1093–1110.
https://doi.org/10.4007/annals.2005.161.1093 - J.A. Rodr\'{\i}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 - A. Sebö and E. Tannier, On metric generators of graphs, Math. Oper. Res. 29 (2004) 383–393.
https://doi.org/10.1287/moor.1030.0070 - J.M.S. Simões Pereira, A note on the tree realizability of a distance matrix, J. Combin. Theory 6 (1969) 303–310.
https://doi.org/10.1016/S0021-9800(69)80092-X - P.J. Slater, Leaves of trees, Congr. Numer. 14 (1975) 549–559.
- Ye.A. Smolenskii, A method for the linear recording of graphs, U.S.S.R. Comput. Math. and Math. Phys. 2 (1962) 396–397.
https://doi.org/10.1016/0041-5553(63)90418-X - P. Stefanov, G. Uhlmann and A. Vasy, Boundary rigidity with partial data, J. Amer. Math. Soc. 29 (2016) 299–332.
https://doi.org/10.1090/jams/846 - S. Steinerberger, The boundary of a graph and its isoperimetric inequality, Discrete Appl. Math. 338 (2023) 125–134.
https://doi.org/10.1016/j.dam.2023.05.026 - G. Uhlmann, Inverse problems: seeing the unseen, Bull. Math. Sci. 4 (2014) 209–279.
https://doi.org/10.1007/s13373-014-0051-9 - S.M. Ulam, A collection of mathematical problems, in: Interscience Tracts in Pure and Applied Mathematics 8, Interscience Publishers (1960).
- M.S. Waterman, T.F. Smith, M. Singh and W.A. Beyer, Additive evolutionary trees, J. Theoret. Biol. 64 (1977) 199–213.
https://doi.org/10.1016/0022-5193(77)90351-4 - K.A. Zareckii, Constructing a tree on the basis of a set of distances between the hanging vertices, Uspekhi Mat. Nauk 20(6) (1965) 90–92, in Russian.
Close