18 problems

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…

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…

Product-formula conjecture. The number of successive vertex orderings satisfies

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…

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

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…

Let $x,y,z$ be indeterminate edge weights, and let $A^{(i)}_{a,b,c}(x,y,z)$ and $F^{(i)}_{a,b,c}(x,y,z)$, for $i=1,2,3$, be the corresponding weighted versions of the graphs…

For fixed $d\geq 3$, let $CAY_d(n)$ be the number of isomorphism classes of $d$-valent Cayley graphs of order at most $n$, and let $GRR_d(n)$ count those that are graphical regular…

For fixed $d\geq 3$, let $VT_d(n)$ be the number of isomorphism classes of $d$-valent vertex-transitive graphs of order at most $n$, and let $CAY_d(n)$ count the corresponding Cayl…

Let $d\text{-valent}$ vertex-transitive graphs, Cayley graphs, and graphical regular representations (GRRs) be counted up to order at most $n$ by $VT_d(n)$, $CAY_d(n)$, and…