99 problems

Let $G$ be a simple finite graph with at least three vertices. For each vertex $v\in V(G)$, let $G-v$ be the induced subgraph obtained by deleting $v$, and let $D(G)$ be the multis…

Let $G$ be a simple finite graph with at least four vertices. Let $D(G)$ be the multiset of isomorphism classes of the vertex-deleted subgraphs $G-v$, and let…

For a finite graph $G$, a card is the isomorphism type of a vertex-deleted subgraph $G\setminus v$, and the multiset of all cards is called the deck of $G$. Ulam's reconstruction c…

Let $G$ be a finite simple undirected graph. Its $1$-vertex deck is the multiset of isomorphism types of the graphs obtained by deleting one vertex from $G$. The Reconstruction Con…

Hamilton-cycle reconstruction conjecture. There are constants $0\leq c<1$ and $n_0\geq 0$ such that, for all integers $n\geq n_0$, the number of Hamilton cycles of an $n$-vertex gr…

Ulam–Kelly reconstruction conjecture. A graph of order $n$ is uniquely determined by the multiset of its subgraphs of order $n-1$.

For an $n$-vertex graph, the $m$-deck is the multiset of its unlabeled induced $m$-vertex subgraphs, and a family of graphs is weakly $celltext{ell}$-reconstructible if no two grap…

Let $G$ be a graph on $n$ vertices. For each vertex $v\in V(G)$, let $G_v$ be the subgraph obtained by deleting $v$ from $G$, and let … be the multiset of all vertex-deleted subgra…

Kelly's conjecture. There exists a threshold $M_l$ such that every graph with at least $M_l$ vertices is $l$-reconstructible.

Let $G$ and $H$ be graphs on $n$ vertices, where one is a tree and the other is a connected non-tree. A common card is an unlabeled graph occurring as a card in the decks of both…

Let $G$ be a graph, let $F_k(G)$ denote its $k$-token graph, and let a $k$-token reconstruction family of $F_k(G)$ be a family of subsets as defined in the source. Let…

For a graph $G$, its deck is the multiset of subgraphs obtained by deleting a single vertex from $G$. Reconstruction Conjecture. Every graph $G$ is uniquely determined by its deck.…

Cubical-polytope reconstruction conjecture. Every cubical polytope can be reconstructed from its dual graph.

Graph reconstruction conjecture. The deck of $G$ determines $G$ up to isomorphism.

Homomorphism cancellation conjecture. If, for all graphs $G,H\in\mathcal{G}$,

Let $\mathcal{T}(X_0)$ be a discrete generation pedigree of order $n$ whose population has the same size in every generation. The pedigree is $r$-reconstructible if it is determine…

Let $\mathcal{T}(X_0)$ be a pedigree of order $n$. A pedigree is $(n-1)$-reconstructible if it is determined up to congruence by the collection of its restrictions to subsets of…

Let $X$ be a finite simple undirected graph with at least three vertices. Its vertex deck $VD(X)$ is the collection of all unlabelled subgraphs obtained from $X$ by deleting one ve…

The New Digraph Reconstruction Conjecture. The source proposes a directed reconstruction conjecture based on the collection of these triples, asserting that this augmented vertex-d…

Let $G$ be a finite simple undirected graph. Its $1$-edge deck is the multiset of isomorphism types of the graphs obtained by deleting one edge from $G$. The Edge-Reconstruction Co…

Pouzet's conjecture. The orbit sums $O_{S_n}(x^{M*})$, as $M*$ ranges over all multigraphs with at least one isolated vertex, generate the invariant ring

Edge-reconstruction conjecture. Every graph with at least four edges is edge-reconstructible.

Graph reconstruction conjecture. Every graph is uniquely reconstructible from its deck; equivalently, any two graphs with at least three vertices are isomorphic if and only if they…

Let $G$ be a planar biconnected graph with minimum degree $\delta(G)\geq 3$, and suppose that $G$ is not maximal planar. Let $\mathcal{D}(G)$ be its vertex-deletion deck. Biconnect…

Let $G=(U,V,E)$ be a bipartite graph with $|U|=u$ and $|V|=v$, and let $\mathcal{D}(G)$ denote its vertex-deletion deck. Assume that $G$ is 2-connected, not regular, and has minimu…