| Popis: |
A set S of vertices in a graph G is a dominating set if every vertex not in S is adjacent to a vertex in S . If, in addition, S is an independent set, then S is an independent dominating set. The domination number γ ( G ) of G is the minimum cardinality of a dominating set in G , while the independent domination number i ( G ) of G is the minimum cardinality of an independent dominating set in G . It is known (Goddard et al., 2012) that if G is a connected 3-regular graph, then i ( G ) ∕ γ ( G ) ≤ 3 ∕ 2 , with equality if and only if G = K 3 , 3 . In this paper, we extend this result to graphs of larger regularity and show that if k ∈ { 4 , 5 , 6 } and G is a connected k -regular graph, then i ( G ) ∕ γ ( G ) ≤ k ∕ 2 , with equality if and only if G = K k , k . |
Full Text from ScienceDirect