148 problems

Let $G$) be a connected $d$-regular graph with adjacency matrix $A$ and $n$ vertices. Let $\xi_1,\xi_2,\ldots,\xi_n$ be orthogonal eigenvectors of $A$, with the conditions stated b…

Mkrtchyan–Petrosyan–Vardanyan conjecture. If

Let $\mathcal{G}_{n,d}$ be the uniform model of random $d$-regular graphs on the vertex set $[n]=\{1,2,\ldots,n\}$. A $p$-orientation is an orientation of a $d$-regular graph in wh…

Let $G$ be a $d$-regular graph with $n$ vertices, and let $i(G)$ denote its number of independent sets. Alon and Kahn's conjecture. One has … This formalized the proposed extremal…

Top-eigenvalue vector limit-point conjecture. For any $d\geq 3$ and any fixed $k$, the set of all limit points of the vectors

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 $G$ be a $d$-regular graph with $n$ vertices, where $d\geq 2$. Its irregularity strength $s(G)$ is the least positive integer $k$ for which there is a weighting…

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…

Jackson's conjecture. For each $d>2$, every $d$-regular oriented graph on $n\leq 4d+1$ vertices has a Hamilton cycle.

For $0\leq t\leq r$, let $m(t,r)$ be the maximum integer $s$ such that every $t$-edge-connected $r$-graph has $s$ pairwise disjoint perfect matchings. The upper-bound conjecture. F…

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. Its chromatic number is denoted by $\chi(G)$, and its dynamic chromatic number, the smallest number of colors in a dynamic proper vertex coloring, is de…

Burris–Schelp conjecture.

Let $G$ be a $2$-factor Hamiltonian $k$-regular bipartite graph, meaning that every $2$-factor of $G$ is a Hamiltonian circuit. Sheehan's conjecture. There are no $2$-factor Hamilt…

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 $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$.…

Maximal-gap conjecture for $\Delta_n$. The interval

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…

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

Let $G$ be a simple, finite, undirected graph with $N$ vertices that is $d$-regular, and let $i(G)$ denote its number of independent sets. The graph $\frac{N}{2d}K_{d,d}$ is the di…

Nonexistence conjecture. There are no $8$-regular $K_3$-irregular graphs.

A subgraph $H\leq G$ of a graph $G$ is a graph $H=(V,E)$ such that $V\subseteq V(G)$ and $E\subseteq E(G)$. A graph is $k$-regular if every vertex has degree $k$. Berge-Sauer conje…

Regular Boesch conjecture. If an $(n,kn/2)$ UMRG exists and has girth $g$, then it has maximum girth among all $k$-regular $(n,kn/2)$-graphs and, among the $k$-regular $(n,kn/2)$-g…

Regular extremal-structure conjecture. For every integer $d\ge3$, there exist constants $C_1$ and $C_2$ such that any $\mu$-minimal $d$-regular graph $G$ of order at least $C_1$ is…

Let $d$-regular graphs be graphs in which every vertex has degree $d$, and call a partition of the vertex set into two parts an internal partition when every vertex has at least as…