Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4650519 | Discrete Mathematics | 2008 | 5 Pages |
Abstract
Let G be a simple graph, and let p be a positive integer. A subset D⊆V(G)D⊆V(G) is a p-dominating set of the graph G , if every vertex v∈V(G)-Dv∈V(G)-D is adjacent to at least p vertices in D. The p-domination number γp(G)γp(G) is the minimum cardinality among the p-dominating sets of G . Note that the 1-domination number γ1(G)γ1(G) is the usual domination number γ(G)γ(G). This definition immediately leads to the inequality γ(G)⩽γ2(G)γ(G)⩽γ2(G).In this paper we present some sufficient as well as some necessary conditions for graphs G with the property that γ2(G)=γ(G)γ2(G)=γ(G). In particular, we characterize all cactus graphs H with γ2(H)=γ(H)γ2(H)=γ(H).
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Adriana Hansberg, Lutz Volkmann,