Displaying similar documents to “The k -domatic number of a graph”

Signed total domination number of a graph

Bohdan Zelinka (2001)

Czechoslovak Mathematical Journal

Similarity:

The signed total domination number of a graph is a certain variant of the domination number. If v is a vertex of a graph G , then N ( v ) is its oper neighbourhood, i.e. the set of all vertices adjacent to v in G . A mapping f : V ( G ) → { - 1 , 1 } , where V ( G ) is the vertex set of G , is called a signed total dominating function (STDF) on G , if ∑ x ∈ N ( v ) f ( x ) ≥ 1 for each v ∈ V ( G ) . The minimum of values ∑ x ∈ V ( G ) f ( x ) , taken over all STDF’s of G , is called the signed total domination number of G and denoted by γ s t ( G ) . A theorem stating lower bounds for γ s t ( G ) is...

On the minus domination number of graphs

Hailong Liu, Liang Sun (2004)

Czechoslovak Mathematical Journal

Similarity:

Let G = ( V , E ) be a simple graph. A 3 -valued function f V ( G ) → { - 1 , 0 , 1 } is said to be a minus dominating function if for every vertex v ∈ V , f ( N [ v ] ) = ∑ u ∈ N [ v ] f ( u ) ≥ 1 , where N [ v ] is the closed neighborhood of v . The weight of a minus dominating function f on G is f ( V ) = ∑ v ∈ V f ( v ) . The minus domination number of a graph G , denoted by γ - ( G ) , equals the minimum weight of a minus dominating function on G . In this paper, the following two results are obtained. (1) If G is a bipartite graph of order n , then γ - ( G ) ≥ 4 n + 1 - 1 - n . (2) For any negative integer k and any positive integer...

A note on the independent domination number of subset graph

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

Czechoslovak Mathematical Journal

Similarity:

The independent domination number i ( G ) (independent number β ( G ) ) is the minimum (maximum) cardinality among all maximal independent sets of G . Haviland (1995) conjectured that any connected regular graph G of order n and degree δ ≤ 1 2 n satisfies i ( G ) ≤ ⌈ 2 n 3 δ ⌉ 1 2 δ . For 1 ≤ k ≤ l ≤ m , the subset graph S m ( k , l ) is the bipartite graph whose vertices are the k - and l -subsets of an m element ground set where two vertices are adjacent if and only if one subset is contained in the other. In this paper, we give a sharp upper bound for i ( S m ( k , l ) ) and...

Restrained domination in unicyclic graphs

Johannes H. Hattingh, Ernst J. Joubert, Marc Loizeaux, Andrew R. Plummer, Lucas van der Merwe (2009)

Discussiones Mathematicae Graph Theory

Similarity:

Let G = (V,E) be a graph. A set S ⊆ V is a restrained dominating set if every vertex in V-S is adjacent to a vertex in S and to a vertex in V-S. The restrained domination number of G, denoted by γ r ( G ) , is the minimum cardinality of a restrained dominating set of G. A unicyclic graph is a connected graph that contains precisely one cycle. We show that if U is a unicyclic graph of order n, then γ r ( U ) ≥ ⎡ n / 3 ⎤ , and provide a characterization of graphs achieving this bound.

Domination in partitioned graphs

Zsolt Tuza, Preben Dahl Vestergaard (2002)

Discussiones Mathematicae Graph Theory

Similarity:

Let V₁, V₂ be a partition of the vertex set in a graph G, and let γ i denote the least number of vertices needed in G to dominate V i . We prove that γ₁+γ₂ ≤ [4/5]|V(G)| for any graph without isolated vertices or edges, and that equality occurs precisely if G consists of disjoint 5-paths and edges between their centers. We also give upper and lower bounds on γ₁+γ₂ for graphs with minimum valency δ, and conjecture that γ₁+γ₂ ≤ [4/(δ+3)]|V(G)| for δ ≤ 5. As δ gets large, however, the largest...