Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
469343 | Computers & Mathematics with Applications | 2010 | 6 Pages |
A vertex subset SS of a graph G=(V,E)G=(V,E) is a double dominating set for GG if |N[v]∩S|≥2|N[v]∩S|≥2 for each vertex v∈Vv∈V, where N[v]={u|uv∈E}∪{v}. The double domination number of GG, denoted by γ×2(G)γ×2(G), is the cardinality of a smallest double dominating set of GG. A graph GG is said to be double domination edge critical if γ×2(G+e)<γ×2(G)γ×2(G+e)<γ×2(G) for any edge e∉Ee∉E. A double domination edge critical graph GG with γ×2(G)=kγ×2(G)=k is called kk-γ×2(G)γ×2(G)-critical . In this paper we first show that GG has a perfect matching if GG is a connected K1,4K1,4-free 4-γ×2(G)γ×2(G)-critical graph of even order ≥6 except a family of graphs. Secondly, we show that GG is bicritical if GG is a 2-connected claw-free 4-γ×2(G)γ×2(G)-critical graph of even order with minimum degree at least 3. Finally, we show that GG is bicritical if GG is a 3-connected K1,4K1,4-free 4-γ×2(G)γ×2(G)-critical graph of even order with minimum degree at least 4.