Displaying similar documents to “Edgeless graphs are the only universal fixers”

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.

On domination number of 4-regular graphs

Hailong Liu, Liang Sun (2004)

Czechoslovak Mathematical Journal

Similarity:

Let G be a simple graph. A subset S ⊆ V is a dominating set of G , if for any vertex v ∈ V - S there exists a vertex u ∈ S such that u v ∈ E ( G ) . The domination number, denoted by γ ( G ) , is the minimum cardinality of a dominating set. In this paper we prove that if G is a 4-regular graph with order n , then γ ( G ) ≤ 4 11 n .

On total restrained domination in graphs

De-xiang Ma, Xue-Gang Chen, Liang Sun (2005)

Czechoslovak Mathematical Journal

Similarity:

In this paper we initiate the study of total restrained domination in graphs. Let G = ( V , E ) be a graph. A total restrained dominating set is a set S ⊆ V where every vertex in V - S is adjacent to a vertex in S as well as to another vertex in V - S , and every vertex in S is adjacent to another vertex in S . The total restrained domination number of G , denoted by γ r t ( G ) , is the smallest cardinality of a total restrained dominating set of G . First, some exact values and sharp bounds for γ r t ( G ) are given in Section 2....