Displaying similar documents to “Minus total domination in graphs”

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....

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 signed majority total domination in graphs

Hua Ming Xing, Liang Sun, Xue-Gang Chen (2005)

Czechoslovak Mathematical Journal

Similarity:

We initiate the study of signed majority total domination in graphs. Let G = ( V , E ) be a simple graph. For any real valued function f V → ℝ and S ⊆ V , let f ( S ) = ∑ v ∈ S f ( v ) . A signed majority total dominating function is a function f V → { - 1 , 1 } such that f ( N ( v ) ) ≥ 1 for at least a half of the vertices v ∈ V . The signed majority total domination number of a graph G is γ m a j t ( G ) = min { f ( V ) ∣ f is a signed majority total dominating function on G } . We research some properties of the signed majority total domination number of a graph G and obtain a few lower bounds of γ m a j t ( G ) . ...

The cobondage number of a graph

V.R. Kulli, B. Janakiram (1996)

Discussiones Mathematicae Graph Theory

Similarity:

A set D of vertices in a graph G = (V,E) is a dominating set of G if every vertex in V-D is adjacent to some vertex in D. The domination number γ(G) of G is the minimum cardinality of a dominating set. We define the cobondage number b c ( G ) of G to be the minimum cardinality among the sets of edges X ⊆ P₂(V) - E, where P₂(V) = X ⊆ V:|X| = 2 such that γ(G+X) < γ(G). In this paper, the exact values of bc(G) for some standard graphs are found and some bounds are obtained. Also, a Nordhaus-Gaddum...

Vertex-disjoint stars in graphs

Katsuhiro Ota (2001)

Discussiones Mathematicae Graph Theory

Similarity:

In this paper, we give a sufficient condition for a graph to contain vertex-disjoint stars of a given size. It is proved that if the minimum degree of the graph is at least k+t-1 and the order is at least (t+1)k + O(t²), then the graph contains k vertex-disjoint copies of a star K 1 , t . The condition on the minimum degree is sharp, and there is an example showing that the term O(t²) for the number of uncovered vertices is necessary in a sense.