34 problems

McKay's conjecture. The identity holds for all even orders, for every $n$ and $r$. It is known for square-free $n$ and has been verified for all orders less than $54$; the conjectu…

Limit-existence conjecture. In the statement above, the limits defining the ratios of logarithmic cardinalities for all three graph families exist; in particular, each correspondin…

Conjectured coefficients.

Novelty conjecture. For several values of the cardinality functions, several other sequences are new.

For a positive integer $n$, let the order density of a class of graphs mean the proportion of positive integers up to $n$ that occur as orders of graphs in that class. Order-densit…

Let $G$ be a strongly regular graph with parameters $\lambda=1$ and $\mu=2$, order $n$, and valency $k$. Let $p_6$ denote the number of hexagons in $G$. Exact hexagon-count conject…

Let $\mathcal{G}_{n,d(n)}$ be the set of labeled $d(n)$-regular graphs with $n$ vertices. Set … Assume that $1\leq d(n)\leq n-2$ and that $nd(n)$ is always even. Wormald–McKay's co…

Point-determining graph conjecture. The number of unlabelled point-determining graphs of a given order equals the number of unlabelled endpoint-free graphs of that order.

Let $d$ be a positive integer and let $n$ satisfy … For a graph $G$, write $i(G)$ for its number of independent sets, $N(G)$ for its number of connected sets, and $N_{dom}(G)$ for…

Let $G=(V,E)$ be a simple planar graph, and let $tr(G)$ be the number of trees in $G$ of all sizes. Planar tree-counting conjecture. The function $tr$ is concise: every positive in…

Let $\mathbf d=(d_1,\ldots,d_n)\in\mathbb N^n$ satisfy $0\le d_i\le n-1$, and let $c(\mathbf d)$ be the number of simple graphs on vertices $v_1,\ldots,v_n$ with $\deg(v_i)=d_i$ fo…

Let $\mathcal{Q}$ be the graph class defined in the preceding construction. A graph class is small if there is a constant $c$ such that the number of its labelled $n$-vertex graphs…

For integers $g\geq 1$, $\ell\geq 0$, and $j\geq 1$, let $\binom{n}{r}$ denote the binomial coefficient, let ${}_2F_1$ denote the Gauss hypergeometric function, and let the product…

Let $r_m(n)$, for $m\geq1$, be the number of Hamiltonian cycles in $P_{m+1}\times P_n$, and let $h_m^c(n)$, for $m\geq1$, be the number of contractible Hamiltonian cycles in…

Let $h_m^c(n)$ and $h_m^{nc}(n)$ denote, respectively, the numbers of contractible and non-contractible Hamiltonian cycles in the grid cylinder graph $P_{m+1}\times C_n$, and let…

Let $g$ be a genus function and let $\mathcal A^g$ be one of the labelled graph classes considered in the paper. Logarithmic-threshold growth-constant conjecture. If $c>0$ is a con…

Let $g$ be a genus function, and let $\mathcal A^g$ denote one of the graph classes considered in the paper, such as $\mathcal E^g$, $\mathcal O\mathcal E^g$,…

Let $\mathcal A^h$ be one of the graph classes considered in the paper, indexed by graphs on $[n]$ embeddable in surfaces of Euler genus at most $h$. Genus-increment growth-ratio c…

Let $S$ be a surface, and let $d4cE^S_n$ denote the class of graphs on $[n]$ embeddable in $S$. Let $d4cP$ be the class of planar graphs, with planar growth constant…

Regular-graph enumeration conjecture. The sequence $a_n$ can be computed in polynomial time in $n$.

Wilf's conjecture. The sequence $a_n$ has no Wilfian formula of type (W1).

Let ${\bf d}= (d_1,\ldots,d_n)$ be a degree sequence, let $g({\bf d})$ denote the number of graphs with degree sequence ${\bf d}$, let $d=\frac{1}{n}\sum_{i=1}^n d_i$, let…

Generating-function identities conjecture. Identities (i.1$^t$)--(i.3$^t$), (i.5$^t$), and (i.6$^t$), and consequently identities (i.4$^t$) and (i.1)--(i.4), are valid in general f…

Generating-function relations conjecture. The relations which emerge from the generating functions for $k=3$ and $p=3,5$ hold for all odd prime $p$.

Let $n$ be the size of a random distance-hereditary split tree, and let the number of its clique nodes and star nodes be measured under the cycle-pointed sampling framework. Linear…