56 problems

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 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 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 $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 $\mathcal{H}_{\operatorname{yper}}=(\Lambda,\mathcal{E})$ and $\mathcal{H}^*_{\operatorname{yper}}=(\Lambda^*,\mathcal{E}^*)$ be hypergraphs based on 3I-hyperedge sets…

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…

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…

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…

Let $G$ be a graph on $n$ vertices, and let a card be an unlabeled vertex-deleted subgraph $G-v$. Bowler–Brown–Fenner conjecture. For $n\geq 44$, it can be determined whether $G$ i…

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…

Modified tree reconstruction conjecture. For $n\ge 2\ell+1$, except when $(n,\ell)\in\{(5,2),(13,6)\}$, every $n$-vertex tree is $\ell$-reconstructible. The threshold on $n$ is kno…

Manvel's conjecture. For each $\ell\in\mathbb{N}$, there exists a threshold $M_\ell$ such that every graph with at least $M_\ell$ vertices is $\ell$-reconstructible.

For $l\in\mathbb{N}$, let an $l$-deck be the multiset of $l$-vertex induced subgraphs of a graph, and call a graph $\ell$-reconstructible if it is determined by its $(n-\ell)$-deck…