223 problems

Let $G$ be a $d$-regular graph, let $A_\sigma$ be the signed adjacency matrix associated with a signing $\sigma$ of $G$, and write $\rho(A_\sigma)=\max_i|\lambda_i(A_\sigma)|$. Bil…

Let $G$) be a simple connected graph with a Hamiltonian cycle $C$. A graph is $k$-regular if every vertex has degree $k$, and a cycle is distinct from $C$ if it is not $C$. Sheehan…

Let $G$ be a $d$-regular graph, and let $i(G)$ denote its number of independent sets. Kahn's conjecture. The upper bound proved for regular bipartite graphs could be extended to al…

Magnant–Martin conjecture. Every $n$-vertex $d$-regular undirected graph has a path partition with at most $n/(d+1)$ paths; this bound would be tight for the disjoint union of…

Let $G$ be a $d$-regular graph with $n$ vertices. A spanning subgraph $H$ has $m(H,i)$ vertices of degree $i$ in $H$, for each $0\le i\le d$. Alon–Wei conjecture. There exists a sp…

Aldous–Fill conjecture. The maximum relaxation time over connected regular graphs with $n$ vertices is

Let $r$ and $n$ be integers with $r\geq 5$ and $n\geq r+3$, and let $G$ be a Hamiltonian $r$-regular graph on $n$ vertices. Haythorpe's conjecture. The graph $G$ has at least … Ham…

Let $G$ be a $t$-connected regular graph on $n$ vertices, with degree at least $n/(t+1)$. Bollobás–Häggkvist conjecture. The graph $G$ is Hamiltonian. This conjecture is known for…

Burris–Schelp conjecture.

Let $G$ be a $\b\Delta$-regular graph with order $n$, and let $\b\lambda_2(G)$ denote its second largest adjacency eigenvalue. Here $\b\Delta$ denotes the common vertex degree, and…

Verstraëte's conjecture. For every graph $H$ and every $\eta>0$, there exists a threshold number $r_0$ such that every $n$-vertex, $r$-regular graph $G$ with $r\ge r_0$ contains a…

Let $G$ be a directed $d$-regular graph on $n$ vertices, and regard a cycle as a directed cycle, with an individual edge allowed to count as a cycle of length two as in the source.…

Let an $(n,d)$-graph be a $d$-regular graph on $n$ vertices, and let $i(G)$ denote its number of independent sets. Granville's conjecture. Every $(n,d)$-graph satisfies … where…

Let $c_d(n)$ denote the exponential growth constant for the maximum number of connected vertex subsets among $d$-regular graphs of order $n$. A Moore graph is a $d$-regular graph o…

A 4-regular graph is a graph in which every vertex has degree 4, and a 3-regular subgraph is a subgraph in which every vertex has degree 3. Berge–Sauer conjecture. Every 4-regular…

Let $A$ be the adjacency matrix of a random $d$-regular graph on $n$ vertices, and let $\lambda(A)$ denote its second eigenvalue in absolute value. Assume that $d\leq n/2$ and that…

Let $l\ge 1$ and $k\ge l$ be integers, and let $G$ be a connected claw-free $(k+l+1)$-regular graph of order $n$. Let $\gamma_{p,k}(G)$ denote the minimum cardinality of a $k$-powe…

Let $G$ be a regular graph, and let its valency be the common degree of its vertices. Its smallest eigenvalue is the least eigenvalue of its adjacency matrix. Woo–Neumaier's conjec…

Let $d_0,d_1,\ldots,d_k\geq1$ satisfy … and let $R(n;d_0,\ldots,d_k)$ be the number of partitions of the edges of $K_n$ into spanning regular subgraphs of degrees $d_0,\ldots,d_k$.…

Let $G$ be a connected $r$-regular graph of order $n$, with $r\ge 3$, and let $k\ge 1$. Write $\gamma_{p,k}(G)$ for the minimum cardinality of a $k$-power dominating set of $G$. As…

Bridge conjecture. Almost all non-Hamiltonian 3-regular graphs contain bridges.

John–Mitchell conjecture. If an incomplete block design is $D$-optimal, $A$-optimal, or $E$-optimal, then it is an RGD, provided that an RGD exists.

Let $G$ be a 3-regular graph on $n$ vertices, and let a Hamiltonian cycle be a simple cycle containing all $n$ vertices of $G$. Eppstein's conjecture. Every 3-regular graph on $n$…

Akbari–Kano conjecture. Every $r$-regular graph has an $\{r-t,t\}$-factor.

El Sahili–Kouider conjecture.