location: Current position: Home >> Scientific Research >> Paper Publications

On the Domination Number of Generalized Petersen Graphs P(ck, k)

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.

Pre One:Improved feedback vertex sets in Kautz digraphs K (d, n)

Next One:Improved Feedback Vertex Sets in Kautz Digraphs K(d, n)