Let G = (V, E) be a graph. A subset S ⊆ V is a dominating set of G, if every vertex u ∈ V - S is dominated by some vertex v ∈ S. The domination number, denoted by γ (G), is the minimum cardinality of a dominating set. For the generalized Petersen graph 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)) ≤ ⌈ frac(3 n, 5) ⌉ and conjectured that the upper bound ⌈ frac(3 n, 5) ⌉ is the exact domination number. In this paper we prove this conjecture.
- Domination number
- Generalized Petersen graphs
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics
- Theoretical Computer Science