**7**

votes

**4**answers

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

**1**

vote

**1**answer

104 views

### edge graph reconstruction conjecture : set vs multi set

Why is the edge reconstruction conjecture stated with the deck defined as the multi set of graphs formed by deleting one edge? Can someone give an example of two graphs such that the edge deleted ...

**4**

votes

**1**answer

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

**3**

votes

**0**answers

79 views

### Reconstructing a function from its variants that negate one argument

Call two functions $g(x_1,\ldots,x_n)$ and $h(x_1,\ldots,x_n)$ from complex numbers to complex numbers equivalent if they are the same up to the order of their arguments. Formally: there is a ...

**4**

votes

**2**answers

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

**10**

votes

**0**answers

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

**16**

votes

**0**answers

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

**5**

votes

**1**answer

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

**8**

votes

**1**answer

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