Name
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,..., 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)) <= n + [n/5], for all n and k. |
Year | Venue | Keywords |
|---|---|---|
2010 | AUSTRALASIAN JOURNAL OF COMBINATORICS | minimum vertex cover,generalized petersen graphs,upper bound,lower bound,discrete mathematics,vertex cover |
Field | DocType | Volume |
Graph,Discrete mathematics,Combinatorics,Vertex (geometry),Modulo,Generalized Petersen graph,Vertex cover,Divisor,Conjecture,Mathematics | Journal | 40 |
ISSN | Citations | PageRank |
2202-3518 | 2 | 0.51 |
References | Authors | |
6 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Babak Behsaz | 1 | 7 | 3.73 |
| Pooya Hatami | 2 | 94 | 14.40 |
| Ebadollah S. Mahmoodian | 3 | 48 | 13.54 |