13 problems

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

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…

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

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

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(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…

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…