Article ID Journal Published Year Pages File Type
420948 Discrete Applied Mathematics 2007 8 Pages PDF
Abstract

In a graph G, a vertex dominates   itself and its neighbors. A subset S⊆V(G)S⊆V(G) is a double dominating set of G if S dominates every vertex of G at least twice. The double domination number  dd(G)dd(G) is the minimum cardinality of a double dominating set of G. The double domination subdivision number  sddd(G)sddd(G) is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the double domination number. In this paper first we establish upper bounds on the double domination subdivision number for arbitrary graphs in terms of vertex degree. Then we present several different conditions on G   which are sufficient to imply that sddd(G)⩽3sddd(G)⩽3. We also prove that 1⩽sddd(T)⩽21⩽sddd(T)⩽2 for every tree T, and characterize the trees T   for which sddd(T)=2sddd(T)=2.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , ,