Open problems in Q-reconstruction of graphs from the abstract edge-subgraph poset

Thatte (Journal of Graph Theory, 2019) introduced the Q-reconstruction problem: determine a finite graph up to isomorphism from the isomorphism class of its weighted edge-subgraph poset $\overline{Q}(G)$, whose elements are the unlabeled edge-subgraphs of $G$ ordered by containment and weighted by subgraph counts. He exhibited explicit families $C_1$, $C_2$, $C_3$ of graphs sharing abstract edge-subgraph posets (finitely many small groups of graphs; stars versus matchings; and graphs differing by interchanged copies of $K_3$ and $K_{1,3}$), and proved that the edge reconstruction conjecture is true if and only if these families are the only graphs that are not $Q$-reconstructible. The paper records the following open problems around that conditional classification: the Lovász-analogue density bound (is every graph with more than half of all possible edges $Q$-reconstructible?); whether failure of the edge reconstruction conjecture would force infinitely many non-$Q$-reconstructible graphs inside Müller's edge-reconstructible range; a Nash-Williams-type switching characterization of non-$Q$-reconstructible graphs; whether graphs can fail $Q$-reconstruction for reasons other than edge-deck failure or the known families; an edge-reconstruction analogue of the doubling phenomenon for induced-subgraph posets; and whether the unlabelled and labelled homomorphism-bijection conjectures are equivalent.

Background

Two classical conjectures frame the problem. The Reconstruction Conjecture of Kelly and Ulam asserts that every finite simple graph on at least three vertices is determined, up to isomorphism, by its deck, the multiset of unlabeled subgraphs obtained by deleting one vertex at a time. The Edge Reconstruction Conjecture (ERC), proposed by Harary in 1964, asserts that every graph with at least four edges is determined by its edge-deck, the multiset of unlabeled subgraphs obtained by deleting one edge at a time. The two conjectures are closely related: Greenwell and Hemminger showed that the deck of a graph with at least four edges and no isolated vertices can be recovered from its edge-deck. Both conjectures remain open; see the surveys of Bondy for their status. The strongest general density results for the ERC are due to Lovász (every graph $G$ with $\epsilon(G)>\binom{\nu(G)}{2}/2$ edges, i.e. more than half of all possible edges, is edge-reconstructible, where $\nu(G)$ and $\epsilon(G)$ denote the numbers of vertices and edges) and Müller (every graph with more than $\nu(G)\log_2\nu(G)$ edges is edge-reconstructible, equivalently every $G$ with $2^{\epsilon(G)-1}>\nu(G)!$). A lemma of Nash-Williams, presented in Bondy's manual, characterises hypothetical counterexamples to the ERC through a switching operation on components, reducing the conjecture to showing that no graph with at least four edges admits a nontrivial switch.

Thatte studied reconstruction from subgraph posets, invariants coarser than decks. An edge-subgraph of $G$ is a subgraph induced by a subset of the edge set $E(G)$ (the subset together with all end-vertices of its edges); for example, deleting one edge of $G$ yields an edge-subgraph. Let $\mathrm{esub}(F,G)$ denote the number of edge-subgraphs of $G$ isomorphic to $F$. The edge-subgraph poset $Q(G)$ is the set of isomorphism classes of nonempty edge-subgraphs of $G$, partially ordered by the edge-subgraph containment relation, and weighted by $w_e(F,F')=\mathrm{esub}(F,F')$. The abstract edge-subgraph poset $\overline{Q}(G)$ is the isomorphism class of this weighted poset: it records which unlabeled edge-subgraphs occur, how they are ordered by containment, and with what multiplicities, but not where they sit inside $G$. A graph $G$ is $Q$-reconstructible if $\overline{Q}(G)$ determines $G$ up to isomorphism (modulo isolated vertices, which are invisible to $Q$, since $\overline{Q}(G)=\overline{Q}(G+K_1)$). Because $\overline{Q}(G)$ can be computed from the edge-deck (the weights $w_e(F,G)$ for proper edge-subgraphs $F$ are recoverable from the edge-deck by the edge version of Kelly's lemma), $Q$-reconstructibility is a strictly stronger demand than edge reconstructibility: a graph that is not edge reconstructible is never $Q$-reconstructible, and edge-reconstructible graphs may fail. For instance, the star $K_{1,m}$ and the matching $mK_2$ ($m$ disjoint edges) have identical abstract edge-subgraph posets for every $m>1$, although both are edge-reconstructible for $m\ge 4$.

The source's main theorem identifies the known failures. Write $C_1$ for a finite list of groups of small graphs with equal abstract edge-subgraph posets, $\{K_3,K_{1,3},3K_2\}$ (the triangle, the three-edge star, and three disjoint edges), $\{P_4,K_{1,2}+K_2\}$, $\{P_4+K_2,T_4\}$, $\{C_4,2K_{1,2}\}$, $\{C_4+K_2,B_1\}$, $\{P_6,B_2\}$, $\{B_3,B_4\}$, where $P_n$ and $C_n$ are the path and cycle on $n$ vertices and $T_4,B_1,\dots,B_4$ are specific small graphs pictured in the paper; $C_2$ for the pairs $\{K_{1,m},mK_2\}$, $m>1$; and $C_3$ for the conjugate pairs $pK_3+qK_{1,3}+F$ and $qK_3+pK_{1,3}+F$ with $p\ne q$ and $F$ any multiset of components drawn from paths, cycles, the paw $S_4$ (a triangle with a pendant edge), the diamond $K_4-e$, and $K_4$. In what follows $C_1$, $C_2$, $C_3$ also denote the graphs occurring in these groups, so that $C_1\cup C_2\cup C_3$ is read as a set of graphs. Interchanging copies of $K_3$ and the claw $K_{1,3}$ never changes the abstract edge-subgraph poset, because every allowed component contains equally many triangles and claws as edge-subgraphs. Thatte proved that the ERC is true if and only if the graphs in $C_1\cup C_2\cup C_3$ are the only graphs that are not $Q$-reconstructible. Thus the $Q$-reconstruction problem, classifying the graphs not determined by their abstract edge-subgraph poset, is settled only conditionally on the ERC.

The same paper also connects the ERC to homomorphism counting. A graph homomorphism from $G$ to $H$ is an adjacency-preserving map $V(G)\to V(H)$, and $\hom(G,H)$ denotes the number of such maps. Lovász proved that $\hom(G,F)=\hom(H,F)$ for all graphs $F$ forces $G\cong H$. Thatte conjectured that any bijection $\pi$ of the set of unlabeled graphs satisfying $\hom(G,H)=\hom(\pi(G),\pi(H))$ for all $G,H$ must be the identity (the unlabelled version), and analogously that any bijection of labeled graphs satisfying the same identities satisfies $\pi(G)\cong G$ for all $G$ (the labelled version); he proved that the ERC implies both, and left open whether the two versions are equivalent.

Problem Statement

Determine, unconditionally, which graphs fail to be $Q$-reconstructible and how reconstruction from the abstract edge-subgraph poset $\overline{Q}(G)$ differs from edge-deck reconstruction. The source states the following concrete open questions, each to be settled by proof or counterexample. Each is an independent deliverable that admits its own resolution, and a full resolution of the objective requires all of them.

(1) Density bound (Lovász analogue): is every graph $G$ with $\epsilon(G)>\binom{\nu(G)}{2}/2$ $Q$-reconstructible?

(2) Infinitude of failures: prove or refute the statement that if the edge reconstruction conjecture is false, then there are infinitely many graphs $G$ with $2^{\epsilon(G)-1}>\nu(G)!$ (graphs that are edge-reconstructible by Müller's theorem) that are not $Q$-reconstructible; preferably with $\epsilon(G)=\binom{\nu(G)}{2}/2$.

(3) Nash-Williams analogue: find, or rule out, a characterisation of the graphs that are not $Q$-reconstructible analogous to the Nash-Williams switching lemma for edge reconstruction.

(4) Gap: let $\mathcal{G}_E$ and $\mathcal{G}_Q$ denote the classes of graphs that are not edge reconstructible and not $Q$-reconstructible, respectively. If the edge reconstruction conjecture is false, are there graphs in $\mathcal{G}_Q\setminus(\mathcal{G}_E\cup C_1\cup C_2\cup C_3)$? An affirmative answer to (2) also answers this part: the graphs it produces are edge-reconstructible and, by their density $2^{\epsilon(G)-1}>\nu(G)!$, avoid the sparse families $C_2$ and $C_3$, while only finitely many can lie in the finite list $C_1$; so this part needs a separate construction only if (2) is refuted.

(5) Doubling: does the doubling phenomenon extend from induced-subgraph posets to edge-subgraph posets: for vertex reconstruction it is known that non-isomorphic graphs $G,H$ with the same deck satisfy $P(2G)=P(2H)$, where $2G$ is two disjoint copies of $G$ and $P(\cdot)$ is the abstract induced-subgraph poset; is there an analogous result for the edge reconstruction problem?

(6) Homomorphism-bijection conjectures: are the unlabelled and labelled versions equivalent, i.e. is the conjecture that every bijection $\pi$ of unlabeled graphs with $\hom(G,H)=\hom(\pi(G),\pi(H))$ for all $G,H$ must be the identity equivalent to the conjecture that every bijection of labeled graphs with the same property satisfies $\pi(G)\cong G$ for all $G$?

By the source's main theorem, a full characterisation of the non-$Q$-reconstructible graphs, or an exhibited graph in $\mathcal{G}_Q\setminus(\mathcal{G}_E\cup C_1\cup C_2\cup C_3)$, settles or refutes the edge reconstruction conjecture itself.

References

1. Bhalchandra D. Thatte, "The edge-subgraph poset of a graph and the edge reconstruction conjecture", Journal of Graph Theory 92 (2019), no. 3, 287-303. DOI: 10.1002/jgt.22454. https://doi.org/10.1002/jgt.22454
2. Bhalchandra D. Thatte, "Subgraph posets and graph reconstruction", preprint, arXiv:math/0609574v3 (2006, revised 18 August 2015). https://arxiv.org/abs/math/0609574
3. Deisiane Lopes Gonçalves and Bhalchandra D. Thatte, "A construction of the abstract induced subgraph poset of a graph from its abstract edge subgraph poset", preprint, arXiv:2012.00466 (2020). https://arxiv.org/abs/2012.00466
4. László Lovász, "A note on the line reconstruction problem", Journal of Combinatorial Theory, Series B 13 (1972), 309-310. DOI: 10.1016/0095-8956(72)90068-8. https://doi.org/10.1016/0095-8956(72)90068-8 (the half-density edge-reconstruction bound)
5. Vladimír Müller, "The edge reconstruction hypothesis is true for graphs with more than n log2 n edges", Journal of Combinatorial Theory, Series B 22 (1977), 281-283. DOI: 10.1016/0095-8956(77)90074-0. https://doi.org/10.1016/0095-8956(77)90074-0
6. D. L. Greenwell and R. L. Hemminger, "Reconstructing graphs", in The Many Facets of Graph Theory, Lecture Notes in Mathematics 110, Springer, 1969, 91-114. DOI: 10.1007/BFb0060110. https://doi.org/10.1007/BFb0060110 (deck recoverable from the edge-deck)
7. J. A. Bondy, "A graph reconstructor's manual", in Surveys in Combinatorics 1991, London Mathematical Society Lecture Note Series 166, Cambridge University Press, 1991, 221-252. DOI: 10.1017/CBO9780511666216.009. https://doi.org/10.1017/CBO9780511666216.009 (survey presenting the reconstruction conjectures and the Nash-Williams switching lemma)
8. J. A. Bondy, "Beautiful conjectures in graph theory", European Journal of Combinatorics 37 (2014), 4-23. DOI: 10.1016/j.ejc.2013.07.006. https://doi.org/10.1016/j.ejc.2013.07.006 (survey of the reconstruction conjectures)
9. Bhalchandra D. Thatte, "Kocay's lemma, Whitney's theorem, and some polynomial invariant reconstruction problems", The Electronic Journal of Combinatorics 12 (2005), no. 1, Article R63. DOI: 10.37236/1960. https://doi.org/10.37236/1960 (source of the doubling phenomenon for induced-subgraph posets)
10. Alexander Clifton, Xiaonan Liu, Reem Mahmoud, and Abhinav Shantanam, "Reconstruction and Edge Reconstruction of Triangle-free Graphs", preprint, arXiv:2210.00338 (2022). https://arxiv.org/abs/2210.00338 (recent special-case progress on the ERC)
11. Maxine E. Calle and Julian J. Gould, "A combinatorial K-theory perspective on the Edge Reconstruction Conjecture in graph theory", preprint, arXiv:2402.14986 (2024). https://arxiv.org/abs/2402.14986 (reformulation of the ERC)