Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4649795 | Discrete Mathematics | 2009 | 12 Pages |
Abstract
Let G=(V,E)G=(V,E) be a graph. A subset S⊆VS⊆V is a dominating set of GG, if every vertex u∈V−Su∈V−S is dominated by some vertex v∈Sv∈S. The domination number, denoted by γ(G)γ(G), is the minimum cardinality of a dominating set. For the generalized Petersen graph G(n)G(n), Behzad et al. [A. Behzad, M. Behzad, C.E. Praeger, On the domination number of the generalized Petersen graphs, Discrete Mathematics 308 (2008) 603–610] proved that γ(G(n))≤⌈3n5⌉ and conjectured that the upper bound ⌈3n5⌉ is the exact domination number. In this paper we prove this conjecture.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Hong Yan, Liying Kang, Guangjun Xu,