Weak reconstructibility of connected graphs with domination number 2 and of connected graphs with $\operatorname{diam}(G)=\operatorname{diam}(\overline{G})=2$: the remaining core of a reduction of the Reconstruction Conjecture

The Reconstruction Conjecture (RC), open since the 1940s, asserts that every finite simple graph on at least three vertices is determined up to isomorphism by its deck, the multiset of unlabeled graphs obtained by deleting one vertex at a time. Aravind and Monikandan (arXiv:2601.00620, January 2026) prove that the class of graphs with domination number $\gamma(G)=2$ is recognizable from the deck and reduce the RC to two weak-reconstructibility statements: (1) every connected graph $G$ with $\gamma(G)=2$ is weakly reconstructible, meaning any graph with the same deck that also has domination number 2 is isomorphic to $G$; and (2) every connected graph $G$ with $\operatorname{diam}(G)=\operatorname{diam}(\overline{G})=2$ is weakly reconstructible. Statement (2) is precisely the surviving open core of the 2003 reduction, and statement (1) opens a domination-based axis with no prior literature; no resolution of either is known in the literature to date. Both statements are open; jointly they are equivalent in strength to the RC.

Background

For a finite simple graph $G$, the graph $G-v$ obtained by deleting a vertex $v$ and its incident edges is called a card, and the multiset $D(G)$ of all cards is the deck of $G$. A graph $H$ with $D(H)=D(G)$ is a reconstruction of $G$; a graph is reconstructible if every reconstruction of it is isomorphic to it. The Reconstruction Conjecture (RC), formulated by Kelly and Ulam in the 1940s, asserts that every graph with at least three vertices is reconstructible. It is one of the foremost open problems of graph theory. Known landmarks: the conjecture has been verified by computer for graphs with at most 11 vertices (McKay 1997), disconnected graphs are reconstructible, and $G$ is reconstructible if and only if its complement $\overline{G}$ (the graph on the same vertex set whose edges are exactly the non-edges of $G$) is reconstructible.

For families of graphs a standard decomposition is used. A family $\mathcal{F}$ is recognizable if every reconstruction of a graph in $\mathcal{F}$ again lies in $\mathcal{F}$, and weakly reconstructible if any reconstruction of a graph in $\mathcal{F}$ that stays within $\mathcal{F}$ is isomorphic to it; a family is reconstructible exactly when it is both. For a recognizable family, weak reconstructibility is thus precisely what remains to be shown in order to reconstruct every member. Two standard parameters enter the two problems studied here: the domination number $\gamma(G)$, the minimum size of a set $S$ of vertices such that every vertex outside $S$ is adjacent to at least one vertex of $S$, and the diameter $\operatorname{diam}(G)$, the largest distance (shortest-path length) between two vertices of $G$.

The two problems studied here continue a reduction program for the RC. Yang Yongzhi (1988) proved the RC holds if and only if every 2-connected graph (a graph that remains connected after deleting any single vertex) is reconstructible. Gupta, Mangal and Paliwal (2003) proved that the RC holds if and only if all graphs of diameter 2 and all graphs with $\operatorname{diam}(G)=\operatorname{diam}(\overline{G})=3$ are reconstructible; they showed that their diameter-based families, including the class $C_1$ of graphs with $\operatorname{diam}(G)=\operatorname{diam}(\overline{G})=2$ — exactly the family of the second problem studied here — are recognizable, so for $C_1$ weak reconstructibility has been the sole remaining gap since 2003. Ramachandran and Monikandan (2009) and Balakumar and Monikandan (2014) refined the reduction to progressively smaller classes of 2-connected graphs (blocks with a vertex lying on more than one induced 4-vertex path; non-geodetic, non-interval-regular blocks), and Devi Priya and Monikandan (2018) reconstructed the distance-hereditary 2-connected graphs (graphs in which every induced path is a shortest path) within the diameter-2 core. All known positive results cover only proper subclasses; for instance, Monikandan's 2021 survey records that separable (non-2-connected) diameter-2 graphs are reconstructible.

Against this backdrop, Aravind and Monikandan (2026) introduce domination structure into the program. They prove that the class of graphs with domination number 2 is recognizable from the deck (graphs with a universal vertex, that is $\gamma(G)=1$, are reconstructible, so $\gamma(G)=2$ is the first open domination level), introduce vertex-pair counting parameters $dv(G,k_1,k_2,k_3)$ and $dav(G,k_1,k_2,k_3)$ refining the earlier path-count parameters $pv$ and $pav$ of Gupta et al., show these parameters are reconstructible from the deck for connected graphs on at least 12 vertices with $\gamma(G)\ge 3$, and use them to reconstruct certain $k$-geodetic graphs (graphs with at most $k$ shortest paths between any two vertices) of diameter 2 under side conditions. Their Theorem 5 shows that all connected graphs are reconstructible if and only if all connected graphs with $\gamma(G)=2$ or $\operatorname{diam}(G)=\operatorname{diam}(\overline{G})=2$ are reconstructible, and combined with Yang Yongzhi's reduction, Theorem 7 gives: the RC is true if and only if all 2-connected graphs $G$ with $\gamma(G)=2$ or $\operatorname{diam}(G)=\operatorname{diam}(\overline{G})=2$ are reconstructible. Since the two families involved are recognizable, the paper's conclusion isolates exactly two remaining tasks, which are the two problems studied here: weak reconstructibility of the connected graphs with $\gamma(G)=2$, and weak reconstructibility of the connected graphs with $\operatorname{diam}(G)=\operatorname{diam}(\overline{G})=2$.

Problem Statement

Let $G$ be a finite simple graph and $\overline{G}$ its complement; let $\gamma(G)$ denote the domination number of $G$ and $\operatorname{diam}(G)$ its diameter. Recall that a family $\mathcal{F}$ of graphs is weakly reconstructible if whenever $G\in\mathcal{F}$ and $H$ is a graph whose deck (the multiset of one-vertex-deleted unlabeled subgraphs) equals the deck of $G$, and $H\in\mathcal{F}$, then $H\cong G$.

Establish or refute the following two statements, isolated by Aravind and Monikandan (2026) as the remaining tasks of their reduction of the Reconstruction Conjecture:

(1) The family of all connected graphs $G$ with $\gamma(G)=2$ is weakly reconstructible: any graph sharing the deck of such a $G$ that is connected and again has domination number 2 is isomorphic to $G$.

(2) The family of all connected graphs $G$ with $\operatorname{diam}(G)=\operatorname{diam}(\overline{G})=2$ is weakly reconstructible: any graph sharing the deck of such a $G$ that is connected and again has diameter 2 in both the graph and its complement is isomorphic to $G$.

The two statements share one joint objective: both families are recognizable from the deck, so proving both statements completes the reduction and yields the full Reconstruction Conjecture, while each statement is an immediate consequence of the RC. A proof of either statement alone is a meaningful partial answer. A refutation of either statement consists of a single explicit pair of non-isomorphic connected graphs with equal decks inside the corresponding family, which would simultaneously refute the Reconstruction Conjecture itself.

References

1. J. Antony Aravind and S. Monikandan, "A Reduction of the Reconstruction Conjecture using Domination and Vertex Pair Parameters", arXiv:2601.00620 (2026). DOI: 10.48550/arXiv.2601.00620, https://arxiv.org/abs/2601.00620
2. Yang Yongzhi, "The reconstruction conjecture is true if all 2-connected graphs are reconstructible", Journal of Graph Theory 12(2):237-243 (1988). DOI: 10.1002/jgt.3190120214, https://doi.org/10.1002/jgt.3190120214
3. S. K. Gupta, Pankaj Mangal, and Vineet Paliwal, "Some work towards the proof of the reconstruction conjecture", Discrete Mathematics 272(2-3):291-296 (2003). DOI: 10.1016/S0012-365X(03)00198-5, https://doi.org/10.1016/S0012-365X(03)00198-5
4. S. Ramachandran and S. Monikandan, "Graph reconstruction conjecture: reductions using complement, connectivity and distance", Bulletin of the Institute of Combinatorics and its Applications 56:103-108 (2009). Zbl: 1175.05096, https://zbmath.org/?q=an%3A1175.05096
5. J. Balakumar and S. Monikandan, "A reduction of the graph reconstruction conjecture", Discussiones Mathematicae Graph Theory 34(3):529-537 (2014). DOI: 10.7151/dmgt.1746, https://doi.org/10.7151/dmgt.1746
6. P. Devi Priya and S. Monikandan, "Reconstruction of distance hereditary 2-connected graphs", Discrete Mathematics 341:2326-2331 (2018). DOI: 10.1016/j.disc.2018.05.003, https://doi.org/10.1016/j.disc.2018.05.003
7. Brendan D. McKay, "Small graphs are reconstructible", Australasian Journal of Combinatorics 15:123-126 (1997). Zbl: 0878.05062, https://zbmath.org/?q=an%3A0878.05062
8. S. Monikandan, "Reconstruction of Graphs", chapter in "Recent Applications in Graph Theory", IntechOpen (online first 2021; book published 2022). DOI: 10.5772/intechopen.98726, https://doi.org/10.5772/intechopen.98726
9. Julian Asilis, Xi Chen, Dutch Hansen, and Shang-Hua Teng, "Semi-Random Graphs, Robust Asymmetry, and Reconstruction", arXiv:2509.21516 (2025). https://arxiv.org/abs/2509.21516
10. S. K. Gupta, Sahil Singla, Akash Khandelwal, Apurv Tiwari, and Srilekha, "Exhaustive Verification of Weak Reconstruction For Self Complementary Graphs", arXiv:1012.5995 (2010). https://arxiv.org/abs/1012.5995
11. Robert John O'Shea and Louis Wilkins, "Vertex-substitution framework verifies the reconstruction conjecture for finite undirected graphs", Information Sciences 654:119858 (2024); corrigendum: Information Sciences 675:120738 (2024). DOI: 10.1016/j.ins.2023.119858; corrigendum DOI: 10.1016/j.ins.2024.120738, https://doi.org/10.1016/j.ins.2023.119858