Article ID Journal Published Year Pages File Type
4650519 Discrete Mathematics 2008 5 Pages PDF
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
, ,