**15**

votes

**0**answers

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$.
...

**3**

votes

**1**answer

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 ...

**5**

votes

**1**answer

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

**0**answers

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 ...

**7**

votes

**3**answers

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 ...

**10**

votes

**0**answers

341 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

**1**answer

704 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 ...