Reconstructibility of rooted neighbourhood multisets, radius, diameter, and per-root subgraph counts from the vertex-deck of a graph

The vertex-deck of a graph is the multiset of its unlabelled vertex-deleted subgraphs. Kelly's lemma shows that, for any graph with fewer vertices, the number of subgraphs of a graph isomorphic to it, and even the number containing a given vertex, is computable from the deck. Gonçalves and Thatte (2023) refined this programme to rooted subgraphs, asking which per-root counts and derived parameters are deck-computable, and proved that the multiset of radius-$k$ rooted neighbourhoods $S_k(G)$ is reconstructible whenever the radius of $G$ exceeds $k$. Several natural regimes remain open: whether $S_1(G)$ is reconstructible for arbitrary graphs; whether the radius and diameter of an arbitrary graph are reconstructible from the vertex-deck; and which rooted four-vertex patterns admit per-root reconstructible counts, where pseudo-similar vertices already obstruct some induced counts.

Background

All graphs are finite and simple. The vertex-deck $D(G)$ of a graph $G$ is the multiset of unlabelled graphs obtained by deleting one vertex of $G$; each member is a card, written $G-v$. The edge deck $ED(G)$ is defined analogously with single edge deletions. The Reconstruction Conjecture (Kelly, 1942, and Ulam, 1960) asserts that every graph on at least three vertices is determined up to isomorphism by its vertex-deck; the analogous edge reconstruction conjecture concerns graphs with at least four edges. Both are open. A parameter or structure of $G$ is called reconstructible if it is determined by $D(G)$ alone (edge reconstructible if determined by $ED(G)$).

Kelly's lemma and its rooted refinement. For graphs $F$ and $G$, let $s(F,G)$ and $i(F,G)$ denote the numbers of subgraphs and of induced subgraphs of $G$ isomorphic to $F$, and let $s(F,G^v)$ and $i(F,G^v)$ count such copies containing a given vertex $v$ of $G$. Kelly's lemma states that when $v(F)<v(G)$ all four quantities are reconstructible, since $s(F,G^v)=s(F,G)-s(F,G-v)$. A copy of $F$ containing $v$ can realize $v$ in several roles, so Gonçalves and Thatte refined the count: for $F$ rooted at a vertex $x$, written $F^x$, the quantity $s(F^x,G^v)$ (respectively $i(F^x,G^v)$) is the number of (induced) copies of $F$ in $G$ whose root coincides with $v$. The key identity is $s(F^x,G)=|\mathrm{Orbit}_F(x)|\,s(F,G)$, where $\mathrm{Orbit}_F(x)$ is the orbit of $x$ under the automorphism group of $F$, that is, the set of vertices of $F$ similar to $x$ (Lemma 2.1 of the source).

Rooted neighbourhoods and metric parameters. For a connected $G$ and a vertex $v$, $G^v_k$ denotes the subgraph rooted at $v$ and induced by all vertices at distance at most $k$ from $v$, and $S_k(G)$ is the multiset $\{G^v_k:v\in V(G)\}$. The radius $r(G)$ is the minimum over vertices of the eccentricity (the maximum distance from that vertex to any other); the diameter is the maximum eccentricity. The source proves that $S_k(G)$ is reconstructible whenever $r(G)>k$ (Proposition 2.2) — the hypothesis guarantees that every $G^v_k$ has fewer vertices than $G$, so a Kelly-type recursion over the deck applies — together with an edge-deck analogue (Proposition 3.3). Using the theorem, due to Walikar and coauthors, that the radius-minimal connected graphs — those $G$ for which $r(G-e)>r(G)$ for every edge $e$ — are exactly the trees, the authors note that the radius of any connected graph that is not a tree is edge reconstructible (Remark 3.4).

The obstruction: pseudo-similar vertices. Two vertices $u,v$ of $G$ are pseudo-similar, in the sense of Godsil and Kocay, if $G-u\cong G-v$ but no automorphism of $G$ maps $u$ to $v$. Such pairs exist, and they show that per-card data is in general not a function of the deck: the same unlabelled card can arise from vertices whose rooted neighbourhoods are non-isomorphic, and specific rooted induced counts $i(F^x,G^v)$ can differ between vertices with identical cards; the source exhibits this for rooted four-vertex patterns such as the path $P_4$ rooted at a leaf.

Problem Statement

The common objective is to determine which rooted local structures and global metric parameters of a graph are computable from its vertex-deck alone, completing the refinement of Kelly's lemma begun by Gonçalves and Thatte. Three linked regimes are open. Each regime is an independent sub-question that may be resolved by proof or by counterexample.

(1) Neighbourhood multiset. Is $S_1(G)=\{G^v_1:v\in V(G)\}$, the multiset of rooted radius-1 neighbourhoods, reconstructible for every connected graph $G$? It is known to be reconstructible when $r(G)>1$ (Proposition 2.2 with $k=1$); the open case is graphs of radius 1, and no proof or counterexample is known.

(2) Metric parameters. Are the radius and the diameter of an arbitrary connected graph reconstructible from the vertex-deck? Neither is known in general; the radius is edge reconstructible for connected non-trees, and the source notes that its reconstructibility result can be applied to classes for which estimates for the radius can be made from the deck (for example bounded-degree graphs and graphs containing a vertex of degree 1), but the general vertex-deck question is open.

(3) Per-root counts for four-vertex rooted patterns. For which rooted graphs $F^x$ are the per-root counts $i(F^x,G^v)$ and $s(F^x,G^v)$ computable from the deck of $G$? All patterns with $v(F)\le 3$ are settled. For rooted graphs on four vertices, some induced counts are provably not reconstructible (via pseudo-similar vertices) while the corresponding subgraph counts and their sums are reconstructible, and for one specific rooted four-vertex pattern (discussed around Equation (8) of the source) the authors state they do not know how to compute the individual induced count $i(F^x,G^v)$.

Structural remark. Each of (1) and (2) is a consequence of the Reconstruction Conjecture: if two graphs on at least three vertices share a deck but differ in $S_1(G)$, radius, or diameter, they form a counterexample to that conjecture. Hence a positive resolution of (1) or (2) is a strict weakening of the Reconstruction Conjecture, while a negative one refutes it. Component (3) is finer: pseudo-similar vertices already produce negative answers for some patterns without affecting the conjecture, so (3) can be settled independently by orbit-counting identities or explicit constructions.

References

1. Deisiane Lopes Gonçalves and Bhalchandra D. Thatte. A refinement of Kelly's lemma for graph reconstruction for counting rooted subgraphs. arXiv:2312.17022 (2023). https://arxiv.org/abs/2312.17022
2. Paul Kelly. A congruence theorem for trees. Pacific Journal of Mathematics 7 (1957) 961-968. doi:10.2140/pjm.1957.7.961, https://doi.org/10.2140/pjm.1957.7.961
3. J. A. Bondy and R. L. Hemminger. Graph reconstruction - a survey. Journal of Graph Theory 1 (1977) 227-268. doi:10.1002/jgt.3190010306, https://doi.org/10.1002/jgt.3190010306
4. J. A. Bondy. A Graph Reconstructor's Manual. Surveys in Combinatorics 1991, London Mathematical Society Lecture Note Series (1991) 221-252. doi:10.1017/cbo9780511666216.009, https://doi.org/10.1017/cbo9780511666216.009
5. C. D. Godsil and W. L. Kocay. Constructing graphs with pairs of pseudo-similar vertices. Journal of Combinatorial Theory, Series B 32 (1982) 146-155. doi:10.1016/0095-8956(82)90030-2, https://doi.org/10.1016/0095-8956(82)90030-2
6. H. B. Walikar, Fred Buckley, and M. K. Itagi. Radius-edge-invariant and diameter-edge-invariant graphs. Discrete Mathematics 272 (2003) 119-126. doi:10.1016/s0012-365x(03)00189-4, https://doi.org/10.1016/s0012-365x(03)00189-4
7. Vladimir Levenshtein, Elena Konstantinova, Eugene Konstantinov, and Sergey Molodtsov. Reconstruction of a graph from 2-vicinities of its vertices. Discrete Applied Mathematics 156 (2008) 1399-1406. doi:10.1016/j.dam.2006.11.016, https://doi.org/10.1016/j.dam.2006.11.016
8. Thomás Jung Spier. Efficient reconstruction of the characteristic polynomial. arXiv:2503.17853 (2025). https://arxiv.org/abs/2503.17853
9. Peter Stark. Generalization and Power of Kocay's Lemma in Graph Reconstruction. arXiv:2509.02604 (2025). https://arxiv.org/abs/2509.02604
10. David Hartman, Aneta Pokorná, Daniel Trlifaj, and Lluís Vena. Reconstructing graphs and their connectivity using graphlets. arXiv:2508.19189 (2025). https://arxiv.org/abs/2508.19189
11. J. Antony Aravind and S. Monikandan. A Reduction of the Reconstruction Conjecture using Domination and Vertex Pair Parameters. arXiv:2601.00620 (2026). https://arxiv.org/abs/2601.00620
12. Emilie Dufresne, Gabriela Jeronimo, Jenny Kenkel, Haydee Lindo, and Nelly Villamizar. Shuffling the Deck: Invariant Theory and the Graph Reconstruction Conjecture. arXiv:2604.16567 (2026). https://arxiv.org/abs/2604.16567