# Tagged Questions

Questions related to graph reconstruction, the problem of reconstructing a graph from a set or deck (multiset) of subgraphs.

312 views

### Is the Poset of Graphs Automorphism-free?

For $n\geq 5$, let $\mathcal {P}_n$ be the set of all isomorphism classes of graphs with n vertices. Give this set the poset structure given by $G \le H$ if and only if $G$ is a subgraph of $H$. ...
661 views

### Reconstruction Conjecture holds for Directed Acyclic Graphs?

Wikipedia's article on the Reconstruction Conjecture mentions that the conjecture is false for digraphs, and refers to two papers by Stockmeyer. As far as I can see, none of the counter-examples in ...
195 views

### Reconstruction Conjecture: are almost all digraphs reconstructible?

The Reconstruction Conjecture for simple graphs remains unresolved. Most attempts I've seen at resolving the conjecture aim at proving it to be true (or partially true). I don't believe there is a ...
376 views

### Reconstruction Conjecture and Partial 2-trees

Reconstruction conjecture says that graphs (with at least three vertices) are determined uniquely by their vertex deleted subgraphs. This conjecture is five decades old. Searching relevant literature,...
980 views

### Reconstruction conjecture: Can other decks do the job?

The standard reconstruction conjecture states that a graph is determined by its deck of vertex-deleted subgraphs. Question: Have other decks been investigated, finding out that only vertex-...
596 views

### Reconstructing graphs with vertices of degree $k$ and $k-1$

The Graph Reconstruction Conjecture claims that any simple graph with 3 or more vertices is reconstructible from its "deck" of vertex-deleted subgraphs. (A nice introduction to this problem is at this ...
740 views

### Reconstruction Conjecture: Group theoretic formulation

As we read from wiki, informally, the reconstruction conjecture in graph theory says that graphs are determined uniquely by their subgraphs. Is there a group-theoretic formulation of this conjecture?...
157 views

### Reconstructing the number of Hamiltonian cycles

As is common terminology in graph reconstruction, given a graph $G$, we call a vertex deleted subgraph of $G$, a card, and call the multiset of all cards, the deck of $G$. The graph reconstruction ...
148 views

### Edge Reconstruction Conjecture

I have seen this question asked at least once before, but not with any real answers. I was reading about the various reconstruction conjectures and equivalents, and I saw that the reconstruction ...