Displaying similar documents to “A note on the domination number of a graph and its complement”

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 .

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

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.

Homogeneously embedding stratified graphs in stratified graphs

Gary Chartrand, Donald W. Vanderjagt, Ping Zhang (2005)

Mathematica Bohemica

Similarity:

A 2-stratified graph G is a graph whose vertex set has been partitioned into two subsets, called the strata or color classes of G . Two 2 -stratified graphs G and H are isomorphic if there exists a color-preserving isomorphism φ from G to H . A 2 -stratified graph G is said to be homogeneously embedded in a 2 -stratified graph H if for every vertex x of G and every vertex y of H , where x and y are colored the same, there exists an induced 2 -stratified subgraph H ' of H containing y and a color-preserving...

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