2,904 problems

Partition-graph de-anonymization conjecture. If a single user is de-anonymized by an optimizing attacker from $G$, the number of remaining perfect matchings is at most the number r…

Let $G$ be a decorated unicyclic graph with cycle length parameter $g$, let $R_G$ be its curvature operator, and let $w^\ast$ denote the Perron metric. Write … and let $\varphi$ be…

Regular-graph self-improvement conjecture. Any $d$-regular graph satisfying $\mathrm{CD}(0,\infty)$ satisfies $\mathrm{CD}(0,d)$.

Let $G_n$ be the partition graph, let $\mathrm{Ax}_n$ and $\mathrm{Sp}_n$ denote its axial and spinal vertex sets, and let…

Let $(s_n)$ be an appropriate sequence of positive integers, and let $G_n$ be the action graph associated with $s_n$. For $n\geq 1$, write $z_n$ for the number of new vertices labe…

Let $G$ be a bipartite graph with independent sets $C_1$ and $C_2$, with $|C_1|=c_1\leq c_2=|C_2|$, as in Theorem. Let ${\mathcal F}_k(G)$ be the $k$-supertoken graph of $G$, and s…

Planar-graph unimodality conjecture. For any planar graph $G$ of order $n$, the sequence $\{\st{G}{k}\}_{k=1}^n$ is unimodal. This property is known for paths, cycles, trees, lolli…

Let $P_k$ and $P_m$ be paths on $k$ and $m$ vertices, respectively, and let $G=P_k\mathbin{\square}P_m$ denote their Cartesian product. For a graph $G$, write ${\mathbb D}(G)$ for…

Almost-all-graphs unimodality conjecture. For almost all graphs $G$, the sequence $c^{\mathcal{P}}_i(G)$, $0\leq i\leq n(G)$, is unimodal.

Path-tree recurrence conjecture. For $0\leq k\leq n$ and all $\ell\geq 0$,

Tree discriminant magnitude homology conjecture. For $k=3,4$,

Let $\mathrm{Fw}_n$ denote the boundary framework, let $L_r(n)$ be the vertices of local simplex dimension $r$, and let $(n)$ and $(1^n)$ be the two antenna vertices. Low-dimension…

Antenna-vertex conjecture. For every $n\geq 4$, the only vertices of local simplex dimension $1$ are the two antenna vertices:

Let $G_n$ be the partition graph, let $K_n$ be its clique complex, let $L_r(n)$ denote the vertices of local simplex dimension $r$, let $\Delta(n)$ be the maximal local simplex dim…

Let $G$ be a graph, and define $\nu(G)$ as the absolute value of $A_D(-1)$ for any orientation $D$ of $G$. An Eulerian graph is a graph in which every vertex has even degree. Euler…

Degree-bounded expected value polynomial conjecture. The polynomial $\mathcal{E}(G,S,q)$ has degree at most $\ell$ if and only if, for every $1\leq k\leq s$,

Let $J_n(x)$ be a linear Jaco graph of order $n\geq1$. A diam-path is a path of diameter length, and let $P_d$ be a primary minimal dom-path, meaning a minimal path from $v_1$ to…

Let $J_n(x)$ be a finite linear Jaco graph and let $X$ be its $\Delta$-set. Non-singleton-Delta-vertex conjecture. The vertex subscripts $i$ for which $v_i$ does not yield a single…

Let $J_n(x)$ be a finite linear Jaco graph of order $n\geq3$, and let $X$ be its $\Delta$-set, equivalently its Jaconian set, consisting of vertices attaining the maximum degree. A…

Let $J_n(x)$ be the finite linear Jaco graph of order $n$, and let $\Delta(J_n(x))$ denote its maximum degree. A sequence is $p$-graphical for a graph family $\mathcal{F}$ when it…

Let $J_\infty(x)$ be the infinite linear Jaco graph, and let $X$ be a $\gamma$-set, that is, a minimum dominating set. The vertex subscripts in the displayed set are…

Equality conjecture.

Let $G_{m,n}$ denote the $m$-by-$n$ grid graph, and let $\gamma_{\{2\}}(G_{m,n})$ be its integer $\{2\}$-domination number. The four-row grid conjecture. For every integer…

Let $G_{m,n}$ denote the $m$-by-$n$ grid graph, and let $\gamma_{\{2\}}(G_{m,n})$ be its integer $\{2\}$-domination number. The three-row grid conjecture. For every positive intege…

Symmetry characterization. $I(G\circ H;x)$ is symmetric for every graph $G$ if and only if $H=K_r-e$ for some $r\geq 2$.