The exact domination number of the generalized Petersen graphs

Hong Yan, Liying Kang, Guangjun Xu

Research output: Journal article publicationJournal articleAcademic researchpeer-review

15 Citations (Scopus)

Abstract

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.
Original languageEnglish
Pages (from-to)2596-2607
Number of pages12
JournalDiscrete Mathematics
Volume309
Issue number8
DOIs
Publication statusPublished - 28 Apr 2009

Keywords

  • Domination number
  • Generalized Petersen graphs

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Theoretical Computer Science

Cite this