Non-da-hypomorphy of hypomorphic nonisomorphic digraph pairs with an isomorphically pasted pair of cards (Ramachandran's Problem 7.6)

Ramachandran's 2023 theory of pastings represents a hypomorph of a graph or digraph through two of its cards and yields a dichotomy for da-hypomorphic pairs (digraphs sharing the same degree-associated deck): either every pair of dacards is dapasted isomorphically in both members, in which case the two are isomorphic, or no pair is, in which case they are not. Problem 7.6 of that paper asks whether every pair of hypomorphic but nonisomorphic digraphs whose common deck contains a pair of cards pasted isomorphically in both members must fail to be da-hypomorphic, i.e., must have different dadecks. An affirmative answer would rule out one of the two possible structural types of counterexample to the Degree-Associated Reconstruction Conjecture (DARC), open since 1981; a negative answer would itself be a counterexample to DARC. The problem remains open: DARC remains open, and no da-counterexample is known.

Background

The reconstruction problem asks whether a finite graph is determined, up to isomorphism, by the multiset of its vertex-deleted subgraphs. For a graph or digraph $G$, the unlabeled subgraph $G-v$ obtained by deleting a vertex $v$ is a card of $G$, and the multiset of all cards is the deck of $G$; two graphs/digraphs with the same deck are called hypomorphic, and $G$ is reconstructible if it is isomorphic to all of its hypomorphs. The Reconstruction Conjecture (RC), posed by Kelly and Ulam around 1960, asserts that every graph on at least three vertices is reconstructible; it is one of the most famous open problems of structural graph theory. Kelly proved in 1957 that trees are reconstructible, and computer searches (McKay 1997, extended by McKay 2022) have verified RC for all graphs on at most 13 vertices, but the general case remains open.

For directed graphs the naive analogue is false. A tournament is an orientation of a complete graph, with exactly one of the two possible arcs between each pair of distinct vertices. Beineke and Parker (1970) exhibited non-reconstructible tournaments, and Stockmeyer constructed nine infinite families of pairs of hypomorphic but nonisomorphic digraphs in his 1981 census and a further infinite family in 1988; together with seven sporadic pairs these remain, as confirmed by McKay's 2022 exhaustive census, the only non-reconstructible digraphs known. To repair the directed case, S. Ramachandran proposed in 1981 the Degree-Associated Reconstruction Conjecture (DARC). For a vertex $v$ of a digraph $D$, the degree triple $dt(v)=(a,b,c)$ records the numbers of out-neighbors, in-neighbors, and strong neighbors of $v$ (a strong neighbor is a vertex $w$ such that both arcs $vw$ and $wv$ are present; the pair of opposite arcs is a biarc, and an arc whose reverse is absent is an unpaired arc). The dacard of $D$ at $v$ is the ordered pair $(D-v,dt(v))$, and the collection of all dacards is the dadeck of $D$; two digraphs with the same dadeck are da-hypomorphic, and $D$ is da-reconstructible if it is isomorphic to all of its da-hypomorphs. DARC asserts that every digraph on at least two vertices is da-reconstructible. Since each dacard contains the card, the dadeck refines the deck, so every da-hypomorphic pair is hypomorphic and da-reconstructibility follows from reconstructibility; accordingly, the source describes DARC as a weaker form of ordinary digraph reconstruction, which is also an extension of RC. DARC is open: no proof and no da-counterexample is known. Degree-associated data is also used in reconstruction questions for graphs, e.g. the degree-associated reconstruction number studied by Barrus and West.

In a 2023 preprint Ramachandran introduced a representation of a hypomorph of a graph or digraph in terms of two of its cards, called a pasting. Given a digraph $G$ and distinct vertices $v_1,v_2$ with cards $A=G-v_1$ and $B=G-v_2$, a pasting of $A$ and $B$ as members of $Deck(G)$ is a digraph $P$ having two distinguished non-adjacent vertices $u$ and $v$, both carrying the label $e$ (the external vertices of the two cards), such that (a) $P-u\cong A$ and $P-v\cong B$, and (b) some digraph $H$ obtained from $P$ by adding the arc $uv$, the arc $vu$, both, or neither (for graphs, $H\in\{P,P+uv\}$) is hypomorphic to $G$; $H$ is a completion of the pasting. A pasting $P$ of $A$ and $B$ as members of $Deck(G)$ is a pasting of $A$ and $B$ in a hypomorph $J$ of $G$ if $J$ itself is a completion of $P$ (Definition 4.2 of the source), that is, $J$ is isomorphic to $P$, $P+uv$, $P+vu$, or $P+uv+vu$; this host-completion requirement distinguishes a pasting in a given member digraph from a pasting whose completion is merely some hypomorph of the host. Two pastings of the same pair of cards are isomorphic if there is a digraph isomorphism between them preserving the external-vertex labels. A pair of cards $A,B$ in the common deck of hypomorphic digraphs $G,H$ is pasted isomorphically in both $G$ and $H$ if there is a pasting of $A,B$ in $G$ and a pasting of $A,B$ in $H$ that are isomorphic as pastings. The corresponding notions with degree triples attached to the labels (dacards, dapastings, a dapasting in a da-hypomorph $J$ when $J$ itself is its completion, dapasted isomorphically) are defined analogously.

This calculus yields two structural theorems. Theorem 5.8: two da-hypomorphs are isomorphic if and only if some pair of dacards in their common dadeck is dapasted isomorphically in both (and, for hypomorphs of a graph, if and only if some pair of cards is pasted isomorphically in both). Theorem 5.11: for any pair of da-hypomorphs, exactly one of two alternatives holds — either every pair of dacards in the common dadeck is dapasted isomorphically in both members, forcing isomorphism, or no pair of dacards is, forcing non-isomorphism. Consequently, any counterexample pair to DARC must realize the second alternative. Ramachandran further proves (Theorem 7.3) that in all but four of the known pairs of non-reconstructible digraphs on at least five vertices the common deck does contain a pair of cards pasted isomorphically in both members, and verifies (Observation 7.5) that none of the known pairs of hypomorphic nonisomorphic digraphs on at least five vertices is a da-hypomorphic pair: the ten known infinite Stockmeyer families lie inside da-reconstructible families, and the sporadic pairs are separated by da-reconstructible parameters. Since essentially all known hypomorphic nonisomorphic digraph pairs possess an isomorphically pasted pair of cards, whether such pairs are automatically non-da-hypomorphic becomes the natural next question, posed by the author as Problem 7.6.

Problem Statement

Problem 7.6 of S. Ramachandran (arXiv:2305.14401, 2023), in the author's own words: 'Are all pairs of hypomorphic but nonisomorphic digraphs with their common deck having a pair of cards which is pasted isomorphically in both its member digraphs non-dahypomorphic?'

Unpacked with the definitions above: let $D$ and $E$ be finite digraphs such that (i) $Deck(D)=Deck(E)$ as multisets (they are hypomorphic), (ii) $D\ncong E$, and (iii) there exist cards $A,B$ in the common deck, a pasting $P_D$ of $A$ and $B$ as members of $Deck(D)$ in $D$ — that is, $D$ itself is a completion of $P_D$, so $D$ is isomorphic to $P_D$, $P_D+uv$, $P_D+vu$, or $P_D+uv+vu$, where $u,v$ are the external vertices of $P_D$ — and a pasting $P_E$ of $A$ and $B$ as members of $Deck(E)$ in $E$, with $E$ itself a completion of $P_E$, such that $P_D$ and $P_E$ are isomorphic as pastings (a digraph isomorphism preserving the external-vertex labels). Must $D$ and $E$ be non-da-hypomorphic, i.e., must $Dadeck(D)\ne Dadeck(E)$?

Both answers are consequential. An affirmative answer proves that one of the two structural types of potential counterexample to DARC admitted by the pasting dichotomy (Theorem 5.11) cannot occur — since all but four of the known non-reconstructible digraph pairs have such isomorphically pasted cards (Theorem 7.3), it would show that those pairs are structurally incapable of yielding a DARC counterexample, while the four exempted pairs are excluded from being da-hypomorphic by the already-proved Observation 7.5; it does not by itself prove DARC. A negative answer produces a pair of nonisomorphic da-hypomorphic digraphs, i.e., a counterexample to DARC itself, of the specific structural type having an isomorphically pasted pair of ordinary cards.

References

1. S. Ramachandran, Isomorphic pastings and the two possible structures for a pair of graphs having the same deck, arXiv:2305.14401 (2023), doi:10.48550/arXiv.2305.14401, https://arxiv.org/abs/2305.14401 (source of Problem 7.6)
2. S. Ramachandran, On a new digraph reconstruction conjecture, Journal of Combinatorial Theory, Series B 31 (1981) 143-149, doi:10.1016/s0095-8956(81)80019-6, https://doi.org/10.1016/s0095-8956(81)80019-6
3. S. Ramachandran, Are all pairs of hypomorphic digraphs S-isomorphic?, Discrete Applied Mathematics 319 (2022) 556-563, doi:10.1016/j.dam.2021.08.003, https://doi.org/10.1016/j.dam.2021.08.003
4. S. Ramachandran, A property of most of the known non-reconstructible digraphs, AKCE International Journal of Graphs and Combinatorics 19 (2022) 41-48, doi:10.1080/09728600.2022.2057259, https://doi.org/10.1080/09728600.2022.2057259
5. P. 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
6. L. W. Beineke and E. T. Parker, On nonreconstructable tournaments, Journal of Combinatorial Theory 9 (1970) 324-326, doi:10.1016/s0021-9800(70)80088-6, https://doi.org/10.1016/s0021-9800(70)80088-6
7. P. K. Stockmeyer, A census of non-reconstructable digraphs, I: Six related families, Journal of Combinatorial Theory, Series B 31 (1981) 232-239, doi:10.1016/s0095-8956(81)80027-5, https://doi.org/10.1016/s0095-8956(81)80027-5
8. M. D. Barrus and D. B. West, Degree-associated reconstruction number of graphs, Discrete Mathematics 310 (2010) 2600-2612, doi:10.1016/j.disc.2010.03.037, https://doi.org/10.1016/j.disc.2010.03.037
9. B. D. McKay, Small graphs are reconstructible, The Australasian Journal of Combinatorics 15 (1997) 123-126, Zbl 0878.05062, https://dblp.org/rec/journals/ajc/McKay97.html
10. B. D. McKay, Reconstruction of small graphs and digraphs, The Australasian Journal of Combinatorics 83(3) (2022) 448-457, arXiv:2102.01942, https://arxiv.org/abs/2102.01942
11. T. Hosaka, The reconstruction conjecture for finite simple graphs and associated directed graphs, Discrete Mathematics 345 (2022) 112893, doi:10.1016/j.disc.2022.112893, https://arxiv.org/abs/2003.06759
12. E. Dufresne, G. Jeronimo, J. Kenkel, H. Lindo, N. Villamizar, Shuffling the Deck: Invariant Theory and the Graph Reconstruction Conjecture, arXiv:2604.16567 (2026), https://arxiv.org/abs/2604.16567
13. 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