On minimum vertex cover of generalized Petersen graphs

Details On minimum vertex cover of generalized Petersen graphs On minimum vertex cover of generalized Petersen graphs

2010-08-19

arxiv.org/abs/1008.3208v1

Australasian Journal of Combinatorics, Vol. 40 (2007) pp. 253-264

Computer Science

Discrete Mathematics

11 pages, 1 figure,

Scientific paper

For natural numbers $n$ and $k$ ($n > 2k$), a generalized Petersen graph $P(n,k)$, is defined by vertex set $\lbrace u_i,v_i\rbrace$ and edge set $\lbrace u_iu_{i+1},u_iv_i,v_iv_{i+k}\rbrace$; 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$.

Affiliated with

Also associated with

No associations

Rating

On minimum vertex cover 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 On minimum vertex cover of generalized Petersen graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On minimum vertex cover of generalized Petersen graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-134536