48 problems

Let $C_n$ and $C_m$ be cycles with $n,m\geq 3$. A supermagic labeling of a graph with $q$ edges is a bijection from its edge set to $\{1,2,\dots,q\}$ such that the sums of the labe…

Let $G$ and $H$ be graphs, let $G\Box H$ be their Cartesian product, and let $D$ be a dominating set of $G\Box H$. Let $M_G(A)$ denote the family of dominating sets of $G$ associat…

Let $G$ and $H$ be graphs, let $G\Box H$ be their Cartesian product, and let $D$ be a dominating set of $G\Box H$. For each $h\in V(H)$, let $G_h$ be the $G$-layer corresponding to…

For graphs $F$ and $G$, their Cartesian product $F\Box G$ has vertex set $V(F)\times V(G)$, with $(u,v)$ adjacent to $(u',v')$ if and only if either $u=u'$ and $vv'\in E(G)$, or…

Kao's conjecture. If $n\geq 4\Delta(G)-2$ and $G\Box P_n$ is balanced bipartite, then $G\Box P_n$ is hamiltonian.

Cartesian-product precoloring extension conjecture. This precoloring is extendable to a proper edge coloring.

Let $C_m$ and $C_n$ be cycles with $m,n\geq3$, and let $\mathrm{pmd}(G)$ denote the positive matching decomposition number. Positive matching decomposition conjecture for Cartesian…

Let $\Gamma_1$ and $\Gamma_2$ be graphs, let $\Gamma_1\square\Gamma_2$ denote their Cartesian product, and let $\mathrm{pmd}(\Gamma)$ denote the positive matching decomposition num…

Let $G$ and $H$ be graphs, let $G\mathbin{\square}H$ denote their Cartesian product, and let $\operatorname{gp}^-(G)$ denote the lower general position number of $G$. Kruft's conje…

Let $G$ be a graph. A set $S\subseteq V(G)$ is a terminal set if $S$ is a general position set of $G$ and adding any vertex $u\in V(G)-S$ to $S$ creates three-in-a-line with $u$ as…

Wang–Wu's conjecture.

Let $G$ and $H$ be non-trivial graphs, and suppose that their Cartesian product $G\square H$ is planar. Planar Cartesian product conjecture. The graph $G\square H$ is interval colo…

A path factor of a graph is a factor whose components are paths on at least two vertices. Let $P_m$ be the path on $m$ vertices, and let $\Delta(G)$ denote the maximum degree of a…

The lower general position product bound.

Let $G^{(1)}$ and $G^{(2)}$ be graphs. For vertices indexed by $i$ and $j$, let ${\boldsymbol p}_i^{(1)}$ and ${\boldsymbol p}_j^{(2)}$ denote their node resistance curvatures, and…

Let $G$ be a graph with maximum degree $\Delta(G)$, and let $K_2$ be the complete graph on two vertices. Consider the Cartesian product $G\square K_2$. A precoloring is extendable…

Let $P_s$ be the path on $s$ vertices and $C_t$ the cycle on $t$ vertices, and let $cmu(G)$ denote the mutual-visibility number of a graph $G$. Mutual-visibility number conjecture.…

Let $G$ be a graph, and consider the Cartesian square $G\times G$. An ordering of the vertices is optimal for the edge-isoperimetric problem (EIP) when it minimizes the number of b…

Let $C_m$ be the cycle graph on $m$ vertices, $K_2$ and $C_3$ the indicated factors, and let $G$ be the Petersen graph. For nonnegative exponents, the displayed Cartesian products…

Let $P_{n_1}$ denote the path on $n_1$ vertices and $K_{n_2}$ the complete graph on $n_2$ vertices. For nonnegative integers $d_1,d_2$ and integers $n_1,n_2\geq 2$, write…

Let $C_{2k}$ be an even cycle and let $C^d_{2k}$ denote the $d$-fold Cartesian product of $C_{2k}$ with itself. A distance-three matching is a matching whose distinct edges are at…

Arc-disjoint hamiltonian paths conjecture. The Cartesian product $C_1\mathbin{\Box}C_2\mathbin{\Box}\cdots\mathbin{\Box}C_r$ has two arc-disjoint hamiltonian paths.

Let $G$ and $H$ be graphs, let $D_G$ and $D_H$ be minimum dominating sets of $G$ and $H$, respectively, and let $A_{G,H}[F_G,F_H]$ denote the graph obtained by the paper's edge-adj…

Rall's conjecture. If $G\Box H$ is well-dominated, then at least one of $G$ or $H$ is a complete graph.

Holub–Lužar–Mihaliková–Mockovčiaková–Soták's stronger conjecture. There exists a constant $c$ such that for all integers $m,n\geq c$,