2011/03/12 by Haoli Wang, Xirong Xu, Wang, Haoli +5
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO
paper · pdf · doi:10.48550/arxiv.1103.2427
13 pages
arxiv created 2011/03/12 · arxiv updated 2015/03/18
Let G=(V(G),E(G)) be a simple connected and undirected graph with vertex set V(G) and edge set E(G). A set S ⊆ V(G) is a dominating set if for each v ∈ V(G) either v ∈ S or v is adjacent to some w ∈ S. That is, S is a dominating set if and only if N[S]=V(G). The domination number γ(G) is the minimum cardinalities of minimal dominating sets. In this paper, we give an improved upper bound on the domination number of generalized Petersen graphs P(ck,k) for c≥ 3 and k≥ 3. We also prove that γ(P(4k,k))=2k+1 for even k, γ(P(5k,k))=3k for all k≥ 1, and γ(P(6k,k))=\lceil(10k)/(3)\rceil for k≥ 1 and k≠ 2.