Independence Number of Generalized Petersen Graphs

Abstract

Determining the size of a maximum independent set of a graph \(G\), denoted by \(\alpha(G)\), is an NP-hard problem. Therefore, many attempts are made to find upper and lower bounds, or exact values of \(\alpha(G)\) for special classes of graphs. This paper is aimed towards studying this problem for the class of generalized Petersen graphs. We find new upper and lower bounds and some exact values for \(\alpha(P(n,k))\). With a computer program, we have obtained exact values for each \(n 2k\). We prove this conjecture for some cases. In particular, we show that if \(n > 3k\), the conjecture is valid. We checked the conjecture with our table for \(n < 78\) and found no inconsistency. Finally, we show that for every fixed \(k\), \(\alpha(P(n,k))\) can be computed using an algorithm with running time \(O(n)\).