22 problems

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

Let $k\ge 2$ be an integer, and define … For a graph $G$, write $D$ for its diameter. Miklavič–Šparl conjecture. For every $n>n_k$, the generalized Petersen graph $GP(n,k)$ is not…

Let $GPG(n,s)$ be the generalized Petersen graph and let $C_n(1,s)$ be the circulant graph with step sizes $1$ and $s$. Let $n\geq 5$ and…

Let $\operatorname{GP}(n,k)$ be the generalized Petersen graph, and let $\operatorname{I}(\operatorname{GP}(n,k),x)$ denote its independence polynomial. For all integers…

Let $n$ and $k$ be integers with $n\geq 2k$, and let $GP(n,k)$ be the generalized Petersen graph with star chromatic index $\chi^\prime_s(GP(n,k))$, the smallest number of colors i…

Let $n\ge 3$ and $1\le k<n/2$. The generalized Petersen graph $GP(n,k)$ is defined by … … For a connected graph $G$, vertices $x$ and $y$ are balanced when $|W_{xy}|=|W_{yx}|$, whe…

Jerebic's conjecture. For any $k\ge 2$, there exists a positive integer $n_0$ such that $GP(n,k)$ is not distance-balanced for every $n\ge n_0$. The conjecture was positively resol…

Let $P(4h+2,2h)$ be the generalized Petersen graph with parameters $4h+2$ and $2h$, where $h\geq 3$. Lin et al.'s conjecture. … This conjecture proposes the exact crossing number f…

Let $G(n,k)$ be a generalized Petersen graph. A semigroup graph is a graph admitting a Cayley representation by a semigroup. The semigroup representation conjecture. Every generali…

Let $G(n,k)$ be a non-bipartite generalized Petersen graph, and let $f$ be an endomorphism of $G(n,k)$. The retract-image conjecture. The image of $f$ is a retract of $G(n,k)$. The…

Let $G(n,k)$ be a generalized Petersen graph, and let ${\rm Cay}(M,C)$ denote a monoid Cayley graph with connection set $C$ of size $2$. The monoid Cayley characterization conjectu…

Zhu–Shao's conjecture. The graph $P(3,1)$ is the unique generalized Petersen graph that does not admit a star $5$-edge-coloring.

Let $GP(n,k)$ be a generalized Petersen graph, and let $c(GP(n,k))$ denote its cop number. The known graphs with cop number $2$ are those with $k=1$, together with those satisfying…

Let $k\geq 2$, and let $GP(3k,k)$ be the generalized Petersen graph. Let $\mathfrak{pr}(G)$ denote its minimum coprime number. The $GP(3k,k)$ minimum-coprime-number conjecture. … T…

Let $GP(n,3)$ be the generalized Petersen graph, with $n\geq 7$ odd, and let $\mathfrak{pr}(G)$ denote its minimum coprime number. The $k=3$ minimum-coprime-number conjecture. For…

Let $GP(n,k)$ be the generalized Petersen graph with $ne 3$ and $1\leq k\leq \left\lfloor (n-1)/2\right\rfloor$. A prime labeling assigns distinct labels from $\{1,\ldots,2n\}$ to…

Let $n,k$ be integers with $1\leq k<n/2$, and let $\mathrm{GP}(n,k)$ be the generalized Petersen graph with vertices $u_0,\ldots,u_{n-1},v_0,\ldots,v_{n-1}$ and edges…

The skewness conjecture. For odd integers $k\geq 5$, one has

The eventual non-$\ell$-distance-balance conjecture. For any $n>n_k$, the graph $GP(n,k)$ is not $\ell$-distance-balanced for any integer $\ell$ with $1\leq\ell<D$. Moreover, $n_k$…

Let $P(9,2)$ be the generalized Petersen graph consisting of two 9-cycles together with the additional edges $a_i b_{2i}$, with indices taken modulo $9$. A triangle-free uniquely 3…

Behzad–Behzad–Praeger conjecture. For every odd $n\geqslant 3$,

Let $P(n,k)$ be the generalized Petersen graph, and let $\beta(P(n,k))$ denote the size of a minimum vertex cover. Behsaz–Hatami–Mahmoodian's conjecture. For all $n$ and $k$, … Sin…