The degree-associated edge-reconstruction number of disconnected graphs and trees

NEW

Problem: Reconstructed conjecture: for finite simple undirected graphs, let $G$ be disconnected, edge-reconstructible, and have all connected components isomorphic to a connected graph $H$. If $\operatorname{ern}(G)>3$, then $H\cong K_{1,r}$, where $r=|E(H)|$. This matches the paper’s definition of edge-cards and edge-reconstruction number.

Result: The conjecture is false.

Let $H$ have vertices $a,b,c,d,x,y$ and edges

Thus $H$ is a $4$-cycle on $c,x,d,y$ with one leaf attached to each of $c,d$. Let

Then $G$ is disconnected and all components are isomorphic to $H$. Also $|E(H)|=6$, but $H\not\cong K_{1,6}$, since its maximum degree is $3$.

There are only two edge-card types of $G$:

Deleting either pendant edge gives type $A$; deleting any of the four cycle edges gives type $B$. Hence $G$ has four $A$-cards and eight $B$-cards.

We show every subdeck of at most three edge-cards is blocked by a nonisomorphic graph.

1. $A^3$ is blocked by

Since $H-ac\cong K_1\sqcup(K_{2,3}-e)$, deleting any edge of the $K_{2,3}$-component of $F_A$ gives an $A$-card. Thus $F_A$ contains at least six $A$-cards.

2. Mixed subdecks $A^2B$ and $AB^2$ are blocked by $F_M:=H\sqcup M$, where

Then $M-ad\cong M-bd\cong H-ac$, while $M-dx\cong M-dy\cong H-cx$. Hence $F_M$ has at least two $A$-cards and two $B$-cards.

3. $B^3$ is blocked by

where $N=H+ad$. Since $N-ad=H$, and also $N-dx\cong H$, $N-dy\cong H$, the graph $F_B$ contains at least three $B$-cards.

Each blocker has 12 vertices and 12 edges but is not isomorphic to $G$: $F_A$ has an isolated component, $F_M$ has a component with degree sequence different from $H$, and $F_B$ has components with 5 and 7 edges.

Therefore no subdeck of at most three edge-cards reconstructs $G$, so $\operatorname{ern}(G)\ge 4$. By Molina’s standard upper bound for disconnected graphs with isomorphic components, $\operatorname{ern}(G)\le |E(H)|+2=8$, so $\operatorname{ern}(G)>3$. Thus $G$ satisfies the conjecture’s hypothesis while $H$ is not a star.

Verification audit: the graph is finite, simple, disconnected, has two isomorphic nontrivial components, and has at least four edges. The blockers are explicit nonisomorphic graphs whose edge-decks contain every possible subdeck of size at most three. The conclusion of the conjecture fails.

Citation: Counterexample given here. Definitions and conjecture: Kevin J. Asciak, arXiv:1608.01158. Upper bound used: R. Molina, “The edge reconstruction number of a disconnected graph,” J. Graph Theory 19(3):375–384, 1995.