57 problems

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…

Let $\mathcal{M}$ be the class of finite maximal planar graphs. For $G\in\mathcal{M}$, an edge card is a graph of the form $G-e$, where $e\in E(G)$. Define…

Let $G$ be a finite simple undirected graph. For each vertex $v\in V(G)$, let $G_v=[G-v]_{\cong}$ be its card, and let … be its deck. The graph $G$ is reconstructible if every grap…

Let $G$ be a graph. An edge-deck is the multiset … A graph is edge-reconstructible if it is uniquely determined, up to isomorphism, by its edge-deck. Harary's Edge Reconstruction C…

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…

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…

Let $G$ be an infinite graph with vertex set $E$, and let $\deg(x)$ denote the degree of $x$. Ulam reconstruction conjecture. If … then $G$ is Ulam-reconstructible. The source give…

Let $Hom(F,G)$ denote the number of graph homomorphisms from $F$ to $G$, and let $\mathcal{G}$ be the family of all graphs. For a family of graphs $\mathcal{F}$, say that…

Kelly's conjecture. For $l\in\mathbb{N}$, there is an integer $M_l$ such that any graph with at least $M_l$ vertices is reconstructible from its deck of cards obtained by deleting…

Let $G$ be a locally finite tree. A graph $G$ is reconstructible if every graph hypomorphic to $G$ is isomorphic to $G$, where hypomorphism means that there is a bijection between…

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

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

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

Let $X$ be the leaf set, and let $N_1$ and $N_2$ be binary normal networks on $X$ with no near-sibling reticulations. Write $R(N)$ for the set of rooted triples displayed by a netw…

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 $\mathcal{A}=\{H_1,\dots,H_n\}$ be a real arrangement in $\mathbb{R}^\ell$. A generalized tope graph $\operatorname{\widetilde{\mathcal{T}}}(y_1,\dots,y_n)$ is the graph constr…

Let $G$ be an interval graph. A graph is called BDM-constructible if it is uniquely determined by its boundary distance matrix (with the relevant order and boundary fixed). Interva…

Let $\mathcal{H}_{\operatorname{yper}}=(\Lambda,\mathcal{E})$ and $\mathcal{H}^*_{\operatorname{yper}}=(\Lambda^*,\mathcal{E}^*)$ be hypergraphs based on 3I-hyperedge sets…

Harary's reconstruction conjecture. If $\operatorname{Deck}(G)=\operatorname{Deck}(H)$ for some graph $H$, then $G\cong H$.

Let $G_1$ and $G_2$ be graphs. For each vertex $v$, let $\rho_{r_v^{(2)}}(k)$ denote the corresponding restrained chromatic polynomial, and consider the multiset of these polynomia…

Giro et al.'s reconstruction conjecture. For every $\varepsilon>0$ and every $p\geq(1+\varepsilon)/n$, with high probability there exists a subset $V'\subseteq[n]$ of size…

Let $T$ be a finite tree, and let $\operatorname{crn}(T)$ denote its class reconstruction number. For the class of trees, write…

Let $G$ be a bipartite graph and $H$ a non-bipartite graph, both on $n$ vertices. A common card is an unlabeled vertex-deleted subgraph occurring in the decks of both graphs. Bipar…