Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4649643 | Discrete Mathematics | 2009 | 7 Pages |
In a graph GG a vertex vv dominates all its neighbors and itself. A set DD of vertices of GG is (vertex) dominating set if each vertex of GG is dominated by at least one vertex in DD. The (vertex) domination number of GG, denoted by γ(G)γ(G), is the cardinality of a minimum dominating set of GG. A set DD of vertices in GG is efficient dominating set if every vertex of GG is dominated by exactly one vertex of DD. For natural numbers nn and kk, where n>2kn>2k, a generalized Petersen graphP(n,k)P(n,k) is obtained by letting its vertex set be {u1,u2,…,un}∪{v1,v2,…,vn}{u1,u2,…,un}∪{v1,v2,…,vn} and its edge set be the union of {uiui+1,uivi,vivi+l}{uiui+1,uivi,vivi+l} over 1≤i≤n1≤i≤n, where subscripts are reduced modulo nn. We prove a necessary and sufficient condition for these graphs to have an efficient dominating set, and we determine exact values of γ(P(n,k))γ(P(n,k)) for k∈{1,2,3}k∈{1,2,3}. Also we prove that for an odd number kk, γ(P(n,k))=n2+O(k) and for an even number k>2k>2, γ(P(n,k))≤5n9+O(k).