Independence number of generalized Petersen graphs

Details Independence number of generalized Petersen graphs Independence number of generalized Petersen graphs

2010-08-16

arxiv.org/abs/1008.2583v2

Mathematics

Combinatorics

Scientific paper

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 toward 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<78$. In \cite{MR2381433} it is conjectured that $\beta(P(n, k)) \leq n + \lceil\frac{n}{5}\rceil $, for all $n$ and $k$. 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 it had no inconsistency. Finally, we show that for every fix $k$, $\alpha(P(n, k))$ can be computed using an algorithm with running time O(n).

Affiliated with

Also associated with

No associations

Rating

Independence number of generalized Petersen graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Independence number of generalized Petersen graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Independence number of generalized Petersen graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-176983