On minimum vertex cover of generalized Petersen graphs

Abstract

For natural numbers $n$ and $k$ ($n>2k$), a generalized Petersen graph $P(n,k)$, is defined by vertex set $\{u_i,v_i\}$ and edge set $\{u_i{u}_{i+1},u_i{v}_i,v_i{v}_{i+k}\}$; where $i=1,2,\dots ,n$ and subscripts are reduced modulo $n$. Here first, we characterize minimum vertex covers in generalized Petersen graphs. Second, we present a lower bound and some upper bounds for $\beta (P(n,k))$, the size of minimum vertex cover of $P(n,k)$. Third, in some cases, we determine the exact values of $\beta (P(n,k))$. Our conjecture is that $\beta (P(n,k))\le n+\lceil \frac{n}{5}\rceil$, for all $n$ and $k$.

11 pages, 1 figure,

Cited by in corpus (1)

• Algorithms for Silver Coloring of Generalized Petersen Graphs