7 problems

A graph $G$ with $m$ edges is graceful if there is an injection $f:V(G)\rightarrow\{0,1,\ldots,m\}$ such that the edge labels $|f(x)-f(y)|$, for edges $xy$, are pairwise distinct.…

Let $T$ be a tree with a perfect matching. An adding-edge-subtracting dual graph transformation replaces an edge $u_{k-1}v_{k-1}\in E(H_{k-1})$ by an edge $x_ky_k\notin E(H_{k-1})$…

Let $n\geq 1$, and let $K_{2n+1}$ be the complete graph on $2n+1$ vertices. Ringel–Kotzig decomposition conjecture. The graph $K_{2n+1}$ can be decomposed into $2n+1$ subgraphs, al…

Let $C_n$ be a cycle of length $n\geq 3$, and let $C_n^t$ be the graph obtained from the union of $t$ copies of $C_n$ with one vertex in common, called the central vertex. A graph…

Let $\Gamma$ be a zillion graph with $\omega$ odd cycles and $\mu$ even cycles, and let $|E(\Gamma)|$ denote its number of edges. Edge-size conjecture. There exist a quadratic poly…

A zillion graph is a graph whose components consist of cycles and exactly one path. Let $s$ be the number of cycles, and let the path have length at least $f(s)$. A zillion graph i…

A zillion graph is a graph whose components consist of cycles and exactly one path, as described in the source, and graceful means that it admits a graceful labeling. Let $s$ be th…