Displaying similar documents to “On domination number of 4-regular graphs”

A note on the domination number of a graph and its complement

Dănuţ Marcu (2001)

Mathematica Bohemica

Similarity:

If G is a simple graph of size n without isolated vertices and G ¯ is its complement, we show that the domination numbers of G and G ¯ satisfy γ ( G ) + γ ( G ¯ ) n - δ + 2 if γ ( G ) > 3 , δ + 3 if γ ( G ¯ ) > 3 , where δ is the minimum degree of vertices in G .

A bound on the k -domination number of a graph

Lutz Volkmann (2010)

Czechoslovak Mathematical Journal

Similarity:

Let G be a graph with vertex set V ( G ) , and let k 1 be an integer. A subset D V ( G ) is called a if every vertex v V ( G ) - D has at least k neighbors in D . The k -domination number γ k ( G ) of G is the minimum cardinality of a k -dominating set in G . If G is a graph with minimum degree δ ( G ) k + 1 , then we prove that γ k + 1 ( G ) | V ( G ) | + γ k ( G ) 2 . In addition, we present a characterization of a special class of graphs attaining equality in this inequality.

Inequalities involving independence domination, f -domination, connected and total f -domination numbers

San Ming Zhou (2000)

Czechoslovak Mathematical Journal

Similarity:

Let f be an integer-valued function defined on the vertex set V ( G ) of a graph G . A subset D of V ( G ) is an f -dominating set if each vertex x outside D is adjacent to at least f ( x ) vertices in D . The minimum number of vertices in an f -dominating set is defined to be the f -domination number, denoted by γ f ( G ) . In a similar way one can define the connected and total f -domination numbers γ c , f ( G ) and γ t , f ( G ) . If f ( x ) = 1 for all vertices x , then these are the ordinary domination number, connected domination number and total...