Abstract
A graph is \(\ell \)-reconstructible if it is determined by its multiset of induced subgraphs obtained by deleting \(\ell \) vertices. For graphs with at least six vertices, we prove that all graphs in a family containing all strongly regular graphs and most 2-partially distance-regular graphs are 2-reconstructible.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
The k-deck of an n-vertex graph is the multiset of its \(\left( {\begin{array}{c}n\\ k\end{array}}\right) \) induced subgraphs with k vertices. The famous Reconstruction Conjecture of Ulam [7, 15] asserts that when \(n\ge 3\), every n-vertex graph is determined by its \((n-1)\)-deck. One can consider more generally whether an n-vertex graph is determined by its \((n-\ell )\)-deck. A graph or graph property is \(\ell \)-reconstructible if it is determined by the deck obtained by deleting \(\ell \) vertices. In light of the following observation, it is natural to seek the maximum \(\ell \) such that a graph is \(\ell \)-reconstructible. The observation holds because each card in the \(k'\)-deck appears as an induced subgraph in the same number of cards in the k-deck.
Observation 1
For \(k'<k\), the k-deck of a graph determines the \(k'\)-deck.
Motivated by this observation, Manvel [11, 12] posed a more general version of the Reconstruction Conjecture, and he called this more general version “Kelly’s Conjecture”.
Conjecture 2
([11, 12]) For each natural number \(\ell \), there is a threshold \(M_\ell \) such that every graph with at least \(M_\ell \) vertices is \(\ell \)-reconstructible.
The original Reconstruction Conjecture is \(M_1=3\). Since the graph \(C_4+K_1\) and the tree \(K_{1,3}'\) obtained by subdividing one edge of \(K_{1,3}\) have the same 3-deck, \(M_2\ge 6\). Since \(P_{2\ell }\) and \(C_{\ell +1}+P_{\ell -1}\) have the same \(\ell \)-deck (Lemma 4.10 of [14]), in general \(M_\ell \ge 2\ell +1\), and a result of Nýdl [13] implies that \(M_\ell \), if it exists, must grow superlinearly. (We use \(C_n,P_n,K_n\) for the cycle, path, and complete graph with n vertices, \(K_{r,s}\) for the complete bipartite graph with parts of sizes r and s, and \(G+H\) for the disjoint union of graphs G and H. Our graphs have no loops or multi-edges.)
Kostochka and West [10] surveyed results on \(\ell \)-reconstructibility of graphs. One stream of research is to prove that graphs in a particular family are \(\ell \)-reconstructible. We consider 2-reconstructibility of special families of regular graphs, where a graph is regular if all vertices have the same degree. One of the first results about reconstruction is that regular graphs having at least three vertices are 1-reconstructible (Kelly [8]). By Observation 1, the \((n-1)\)-deck of a graph G determines the 2-deck and hence the number of edges, so in each card of the \((n-1)\)-deck we know the degree of the missing vertex. We thus recognize from the deck that G is k-regular, and in any card the neighbors of the missing vertex are those having degree \(k-1\) in the card.
Motivated by this elementary result in Kelly’s work, Bojan Mohar (personal communication) asked whether sufficiently large regular graphs are 2-reconstructible. Chernyak [4] proved that the degree list is 2-reconstructible for graphs with at least six vertices (note that \(C_4+K_1\) and \(K_{1,3}'\) are 5-vertex graphs having the same 3-deck but different degree lists). However, knowing that the graph is k-regular generally does not by itself determine which vertices having degree \(k-1\) in a card are adjacent to which of the two missing vertices. Nevertheless, Kostochka, Nahvi, West, and Zirlin [9] proved that 3-regular graphs are 2-reconstructible.
With 2-reconstructibility of general k-regular graphs unknown, we consider a restricted family of k-regular graphs. A graph is strongly regular with parameters \((k,\lambda ,\mu )\) if it is k-regular, every two adjacent vertices have exactly \(\lambda \) common neighbors, and every two nonadjacent vertices have exactly \(\mu \) common neighbors. Discussion of strongly regular graphs and their properties can be found for example in the books by van Lint and Wilson [17] and by Brouwer and van Maldeghem [1]. We will prove the following.
Theorem 3
Strongly regular graphs with at least six vertices are 2-reconstructible.
Most of our argument for Theorem 3 applies to graphs in a more general family. A graph is distance-regular if for any two vertices u and v, the number of vertices at distance i from u and distance j from v depends only on the distance between u and v, not on the choice of the vertices. For graphs with diameter d, an equivalent condition is the existence of parameters \((b_{0},\ldots ,b_{d-1};c_{1},\ldots ,c_{d})\) (called the intersection array of G) such that for all \(u,v\in V(G)\) separated by distance m, the numbers of neighbors of u having distance \(m+1\) or \(m-1\) from v are \(b_m\) and \(c_m\), respectively (Brouwer, Cohen, and Neumaier [3]). A strongly regular graph having parameters \((k,\lambda ,\mu )\) with \(\mu \ge 1\) is distance-regular with intersection array \((k,k-\lambda -1; 1,\mu )\). In fact, a graph that is not a disjoint union of complete graphs is strongly regular if and only if it is distance-regular with diameter 2 (Biggs [2]).
We consider in fact a more general family that includes all distance-regular graphs. Let a weakly distance-regular graph with parameters \((k,\lambda ,\mu ')\) be a k-regular graph in which any two adjacent vertices have \(\lambda \) common neighbors and any two vertices separated by distance 2 have \(\mu '\) common neighbors. Trivially, every strongly regular graph is weakly distance-regular. Distance-regular graphs that are regular of degree k are weakly distance-regular with \(\lambda =k-b_1-1\) and \(\mu '=c_2\), but no conditions are placed on vertices separated by distance more than 2.
In fact, the family of weakly distance-regular graphs is the same as another family generalizing distance-regular graphs. The distance-r matrix \(A_r\) of a graph G is the 0, 1-matrix in which position (i, j) is 1 if and only if the distance between \(v_i\) and \(v_j\) is r, so always \(A_0\) is the identity matrix and \(A_1\) is the adjacency matrix A. A graph is t-partially distance-regular (see [5, 6]) if for all r with \(0\le r\le t\) there is a polynomial \(f_r\) of degree r such that \(A_r=f_r(A)\). This definition is motivated by algebraic considerations. (Note: [18] uses a different definition for this term.)
When G is weakly distance-regular with parameters \((k,\lambda ,\mu ')\), the matrix \(A^2\) has k on the diagonal, \(\lambda \) in positions for adjacent vertices, \(\mu '\) in positions for pairs at distance 2, and 0 in positions for pairs at greater distance. This yields \(A_2=(A^2-\lambda A^1-k A^0)/\mu '\), so G is 2-partially distance-regular. Conversely, if G is 2-partially distance-regular with \(f_2(x)=ax^2+bx+c\) (automatically \(f_0(x)=1\) and \(f_1(x)=x\)), then G is weakly distance-regular with \((k,\lambda ,\mu ')=(-c/a,-b/a,1/a)\). The equivalence of these two families is noted in [5]. Another term that has been suggested for this family is “amply regular”, in the book [3] and the survey [16].
We discuss 2-partially distance-regular graphs as weakly distance-regular graphs because that description is what we use in our proof. We will prove the following.
Theorem 4
Weakly distance-regular graphs with at least six vertices and parameters \((k,\lambda ,\mu ')\) with \(\mu '\ge 2\) are 2-reconstructible.
Since there are strongly regular graphs with \(\mu =1\), our two results are independent. As an example of a weakly distance-regular graph that is not strongly regular but has \(\mu '=2t\) and diameter d, consider the graph obtained from a cycle with diameter d by expanding each vertex into an independent set of size t.
It is also reasonable to ask for a family of weakly distance-regular graphs with \(\mu '=1\), not covered by our result. For \(r\ge 2\), let H be a k-regular r-uniform hypergraph with girth at least 5. Form a graph G on the same vertices by letting the vertices of each edge in the hypergraph form a clique. The graph G is weakly distance-regular with parameters \((k(r-1),r-2,1)\).
2 Proof of Theorem 3
A disjoint union of complete graphs with at least six vertices is 2-reconstructible, because we know the degree list and we know that no three vertices induce \(P_3\). Also, connectedness of an n-vertex graph is determined by the \((n-2)\)-deck when \(n\ge 6\) (Manvel [12]). Hence in our discussion we may assume that we are given the deck of an n-vertex connected graph. Note that the disconnected graphs \(K_2+K_2\) and \(P_3+K_1\) have the same 2-deck, though the former is strongly regular.
For strongly regular graphs, our method is analogous to the proof of 1-reconstructibility of regular graphs. We use all the cards in the \((n-2)\)-deck to recognize that any graph having this deck is strongly regular and to determine the parameters \((k,\lambda ,\mu )\). We then use a single card to reconstruct the graph.
It is true that the only 5-vertex graphs that are not 2-reconstructible are not strongly regular, but to avoid special cases we restrict our attention to graphs with at least six vertices.
Proof
Let G be an n-vertex graph, where \(n\ge 6\), and let \({{\mathcal {D}}}\) be the \((n-2)\)-deck of G. By the result of Chernyak [4], \({{\mathcal {D}}}\) determines the degree list of G and hence whether G is k-regular. If so, then any card C in \({{\mathcal {D}}}\) is missing \(2k-1\) or 2k of the kn/2 edges in G, depending on whether the two omitted vertices are adjacent or not. Hence we also see whether the vertices omitted by C are adjacent. Their number of common neighbors is the number of vertices with degree \(k-2\) in C. The graph G is strongly regular with parameters \((k,\lambda ,\mu )\) if and only if that number is \(\lambda \) in each card missing \(2k-1\) edges and \(\mu \) in each card missing 2k edges.
Having recognized that G is strongly regular with parameters \((k,\lambda ,\mu )\), consider one card C, and let u and v be the two omitted vertices. We know whether u and v are adjacent. If G is not \(K_n\), which we can determine, then we may choose C so that u and v are not adjacent. We know the \(\mu \) common neighbors of u and v, and we know the set S of \(2k-2\mu \) vertices that are adjacent to exactly one of \(\{u,v\}\).
For \(x,y\in S\), each of x and y has one neighbor in \(\{u,v\}\); the neighbors may be the same or distinct. The vertices x and y have \(\lambda \) or \(\mu \) common neighbors in G, depending on whether they are adjacent. We see in C whether they are adjacent, so we know their number of common neighbors in G; call it \(\rho \). If x and y have \(\rho \) common neighbors in C, then they have different neighbors in \(\{u,v\}\); if they have \(\rho -1\) common neighbors in C, then they have the same neighbor in \(\{u,v\}\).
This labels each pair of vertices in S as “same” or “different”. Also, the relation defined by “same” is an equivalence relation. Hence it partitions S into two sets. We assign one of those sets to the neighborhood of u and the other to the neighborhood of v. It does not matter which set we assign to which neighborhood, because in both cases we obtain the same graph, and it is G. \(\square \)
A k-regular graph is a Deza graph (generalizing strongly regular graphs) if the number of common neighbors of two distinct vertices takes two possible values, a or b (see http://alg.imm.uran.ru/dezagraphs/info.html). A referee observed that essentially the same argument as above proves 2-reconstructibility of Deza graphs in which a and b are not consecutive.
3 Proof of Theorem 4
The proof of Theorem 3 applies to all connected strongly regular graphs. In particular, we allow the possibility \(\mu =1\). For the more general class of weakly distance-regular graphs, we need to work harder, and the proof does not apply to the case \(\mu '=1\). We restrict to \(\mu '\ge 2\).
Proof
As in the proof of Theorem 3, we may exclude disjoint unions of complete graphs, we know the degree list, and we thus can recognize both that G is k-regular and whether the missing vertices in any card are adjacent in G. The number of common neighbors of the two missing vertices in a card is the number of vertices having degree \(k-2\) in the card. To recognize that G is in the specified class, we check that these numbers all equal \(\lambda \) when the missing vertices are adjacent and equal \(\mu '\) when the missing vertices are nonadjacent and the number is positive. When the number is 0 the distance between the missing vertices in G exceeds 2. Hence we can recognize that G is weakly distance-regular with parameters \((k,\lambda ,\mu ')\) (including when \(\mu '=1\)).
Again choose a card C whose missing vertices u and v are not adjacent, and let S be the set of vertices adjacent to exactly one of \(\{u,v\}\). Again S is the set of vertices having degree \(k-1\) in C. Let x and y be two vertices in S. We see in C whether x and y are adjacent. If so, then they have \(\lambda \) common neighbors in G. Their number of common neighbors in C is then \(\lambda \) or \(\lambda -1\), which tells us whether they have the same neighbor in \(\{u,v\}\).
Since \(\mu '\ge 2\), when x and y are nonadjacent in G we see a common neighbor of x and y in C if and only if the distance between x and y in G is 2. Hence for the pairs of vertices in S separated by distance 2, we can again tell whether their neighbors in \(\{u,v\}\) are the same or different. The pairs of vertices in S that are separated by distance more than 2 in G are those having no common neighbor in C. They must have distinct neighbors in \(\{u,v\}\).
With these arguments, we know for all pairs of vertices in S whether their neighbors in \(\{u,v\}\) are the same or different. Hence again we have two equivalence classes and assign one class to the neighborhood of each of these vertices to complete the reconstruction of G. \(\square \)
Data Availibility Statement
Data sharing is not applicable to this article as no datasets were generated or analysed for this research.
References
Brouwer, A.E., van Maldeghem, H.: Strongly Regular Graphs, Encyclopedia Math. Appl. 182 (Cambridge University Press 2022), xvii+462 pp
Biggs, N.L.: Algebraic Graph Theory, 2nd edn. Cambridge University Press, Cambridge (1993), page 159
Brouwer, A.E., Cohen, A.M., Neumaier, A.: Distance-Regular Graphs, p. 434. Springer-Verlag, Berlin (1989)
Chernyak, Zh.A.: Some additions to an article by B. Manvel: "Some basic observations on Kelly’s conjecture for graphs” (Russian), Vestsī Akad. Navuk BSSR Ser. F\({\bar{i}}\)z.-Mat. Navuk 126, 44–49 (1982)
Dalfó, C., van Dam, E.R., Fiol, M.A., Garriga, E., Gorissen, B.L.: On almost distance-regular graphs. J. Combin. Theory Ser. A 118, 1094–1113 (2011)
Huang, T., Huang, Y., Liu, S.-C., Weng, C.: Partially distance-regular graphs and partially walk-regular graphs (2007), http://jupiter.math.nctu.edu.tw/~weng/papers/11_27.pdf
Kelly, P.J.: On isometric transformations, PhD Thesis, University of Wisconsin–Madison, (1942)
Kelly, P.J.: A congruence theorem for trees. Pacific J. Math. 7, 961–968 (1957)
Kostochka, A.V., Nahvi, M., West, D.B., Zirlin, D.: 3-regular graphs are 2-reconstructible. Eur. J. Combinatorics 91, 10 pages, 103216 (2021)
Kostochka, A.V., West, D.B.: On reconstruction of graphs from the multiset of subgraphs obtained by deleting \(\ell \) vertices. IEEE Trans. Inf. Theory 67, 3278–3286 (2021)
Manvel, B.: On reconstruction of graphs. In: The Many Facets of Graph Theory (Proc. Conf. Western Mich. Univ., Kalamazoo, Mich., 1968), pp. 207–214. Springer, Berlin (1969)
Manvel, B.: Some basic observations on Kelly’s conjecture for graphs. Discrete Math. 8, 181–185 (1974)
Nýdl, V.: Finite undirected graphs which are not reconstructible from their large cardinality subgraphs. Discrete Math. 108, 373–377 (1992)
Spinoza, H., West, D.B.: Reconstruction from the deck of \(k\)-vertex induced subgraphs. J. Graph Theory 90, 497–522 (2019)
Ulam, S.M.: A collection of mathematical problems, Interscience Tracts in Pure and Applied Mathematics, vol. 8. Interscience Publishers, Geneva (1960)
van Dam, E.R., Koolen, J.H., Tanaka, H.: Distance-regular graphs. Electr. J. Combinatorics, Dynamic Survey #22 (2016)
van Lint, J.H., Wilson, R.M.: A Course in Combinatorics, 2nd edn. Cambridge University Press, Cambridge (2001)
Zhang, Y., Liang, X., Koolen, J.H.: The 2-partially distance-regular graphs such that their second largest local eigenvalues are at most one. Discrete Math. 345, 112749 (2022), 12 pages
Acknowledgements
We thank Alexandr V. Kostochka for helpful discussions and Edwin van Dam for pointing out the equivalence between weakly distance-regular and 2-partially distance-regular graphs.
Funding
Research of Douglas B. West was supported by National Natural Science Foundation of China grants NSFC 11871439, 11971439, and U20A2068. Research of Xuding Zhu was supported by National Natural Science Foundation of China grants NSFC 11971438 and U20A2068.
Author information
Authors and Affiliations
Contributions
As is standard in mathematical papers, all authors contributed fully to the paper.
Corresponding author
Ethics declarations
Conflict of interest
The authors have no relevant financial or non-financial interests to disclose.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
West, D.B., Zhu, X. 2-Reconstructibility of Strongly Regular Graphs and 2-Partially Distance-Regular Graphs. Graphs and Combinatorics 39, 94 (2023). https://doi.org/10.1007/s00373-023-02693-1
Received:
Revised:
Accepted:
Published:
DOI: https://doi.org/10.1007/s00373-023-02693-1