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

learn more… | top users | synonyms

15
votes
0answers
206 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$. ...
10
votes
0answers
340 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 ...
8
votes
1answer
703 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 ...
7
votes
3answers
389 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 ...
5
votes
1answer
131 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 ...
3
votes
1answer
97 views

Less general edge reconstruction problem for simple graphs

Let $G$ be a simple graph. Let $E^-(G)$ denote the set of (isomorphism classes) of subgraphs of $G$ that can be obtained by deleting a single edge of $G$. Similarly, let $E^+(G)$ be the set of ...
3
votes
0answers
142 views

If a graph invariant is NP-Hard, is its “deck ratio” NP-Hard as well?

This question is inspired by the Graph Reconstruction Conjecture. Suppose that $\psi$ is some graph invariant and that it is NP-Hard. There is a plethora of examples, of course. Now define ...