240 problems

A Paley graph is the Cayley graph associated with the quadratic residues in a finite field of odd order. A graph is Ramsey when both its clique number and independence number are…

A Hamilton decomposition of a graph is a decomposition of its edge-set into Hamilton cycles. Alspach's conjecture. Every abelian Cayley graph of even degree admits a decomposition…

Babai–Godsil–Imrich–Lovász conjecture. If $(G_n)$ is neither a family of abelian groups with exponent greater than two nor a family of generalized dicyclic groups, then almost all…

Hamiltonian conjecture for Cayley graphs. Every connected Cayley graph on a finite group is Hamiltonian.

Xu's conjecture. Almost all connected Cayley graphs are normal.

Let $G$ be a finite group, let $S$ be a generating set, let $n=|G|$, and let $\mathfrak{D}(\operatorname{Cay}(G,S))$ and $\mathcal{A}(\operatorname{Cay}(G,S))$ denote the graph dia…

McKay–Praeger conjecture. As the order of the (di)graphs grows,

Let $G$ be a group with generating set $S$, and let the Cayley graph $\Gamma$ have vertex set $V(\Gamma)=G$ and edge set … A graph is Hamiltonian if it contains a cycle passing thr…

For $1\leq r<k<n$, let $C(n,k;r)$ be the set of $k$-cycles $\sigma\in S_n$ whose fixed points satisfy $\operatorname{fix}(\sigma)\subseteq\{r+1,\ldots,n\}$. Let…

Let $G$ be a finite group and let $S$ be a generating set for $G$. The Cayley graph of $G$ with respect to $S$ is the graph whose vertices are the elements of $G$, with an edge joi…

Generalized Petersen graph conjecture. Every generalized Petersen graph is an induced subgraph of a minimal Cayley graph.

Let $q$ be an odd prime power, let $\mathbb{F}_{q^2}$ be the finite field with $q^2$ elements, and let $A\subseteq\mathbb{F}_{q^2}$ satisfy $0,1\in A$ and $|A|=q$. Suppose that…

Let $G$ be a finite simple group of Lie type, let $S$ be a non-trivial conjugacy class of $G$, and let $\Gamma(G,S)$ be the Cayley graph generated by $S$. Lubotzky's conjecture. Th…

Let $G$ be a nonabelian finite simple group. A subset $S\subset G$ is symmetric when it is closed under taking inverses, and $\operatorname{Cay}(G,S)$ denotes the Cayley graph of…

Let $\Gamma$ be an abelian group, and let $\mathbb{B}(\Gamma)$ be the Boolean algebra generated by the subgroups of $\Gamma$. A Cayley graph $\operatorname{Cay}(\Gamma,S)$ is integ…

Spiga's element-and-involution conjecture. Except for $\mathrm{PSL}_2(q)$ and a finite number of other cases, every finite non-abelian simple group $G$ contains an element $x$ and…

Let $G=G(\mathbb{F}_2^r,M)$ be a connected Cayley graph defined by a matroid $M$, with generator vectors $v_1,\ldots,v_n$, and let $d(M)$ denote the number of Sylow-$2$ cyclic fact…

Let $n\geq 4$ be an integer and set … The star graph is $\operatorname{Cay}(S_n,S)$. Abdollahi–Vatandoost's conjecture. The star graph is integral, and its set of distinct eigenval…

Let $G$ be a finite non-trivial connected Cayley graph. A Hamilton cycle is a cycle containing every vertex of $G$. Cayley graph Hamilton cycle conjecture. Every finite non-trivial…

Let $S_n$ be the symmetric group, and let $T_n$ be its transposition graph. For $\mathcal{A} \subset S_n$, write $\partial \mathcal{A}$ for its edge-boundary in $T_n$. Let…

Let $(G_i)$ be the family of all non-abelian finite simple groups. A Cayley graph $\mathcal{C}(G_i,S_i)$ is the graph associated with the generating set $S_i$, and a family of grap…

Rapaport–Strasser conjecture. Every connected Cayley graph on a finite group with at least three elements has a Hamilton cycle.

For $0\leq k<n$, let ${{F\!\!J}}(n,k)$ be the full-flag Johnson graph whose vertices are the full flags of $[n]$, with adjacency when exactly $k$ flag components differ. Let $Q$ be…

Let $G$ be a group, let $S$ be a connection set, and let $\operatorname{Cay}(G,S)$ be the corresponding Cayley graph. Consider induced subgraphs whose vertex sets contain more than…

Shapiro's conjecture. A finitely generated group is geodetic if and only if it is plain.