The Independence Number for the Generalized Petersen Graphs

Abstract

Given a graph $G$, an independent set $I(G)$ is a subset of the vertices of $G$ such that no two vertices in $I(G)$ are adjacent. The independence number $\alpha (G)$ is the order of a largest set of independent vertices. In this paper, we study the independence number for the Generalized Petersen graphs, finding both sharp bounds and exact results for subclasses of the Generalized Petersen graphs.