Hits:
Indexed by:期刊论文
Date of Publication:2015-01-01
Journal:ARS COMBINATORIA
Included Journals:SCIE、Scopus
Volume:118
Page Number:33-49
ISSN No.:0381-7032
Key Words:Domination number; Generalized Petersen Graph
Abstract: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 subset of V(C) is a dominating set if for each v is an element of V(G) either v is an element of S or v is adjacent to some w is an element of S. That is, S is a dominating set if and only if N[S] = V(G). The domination number gamma(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 gamma(P(4k, k)) = 2k + 1 for even k, gamma(P(5k, k)) = 3k for all k >= 1, and gamma(P(6k, k)) = inverted right perpendicular (10k)(3) inverted left perpendicular for k >= 1 and k not equal 2.