Displaying similar documents to “Antidomatic number of a graph.”

Partitioning a graph into a dominating set, a total dominating set, and something else

Michael A. Henning, Christian Löwenstein, Dieter Rautenbach (2010)

Discussiones Mathematicae Graph Theory

Similarity:

A recent result of Henning and Southey (A note on graphs with disjoint dominating and total dominating set, Ars Comb. 89 (2008), 159-162) implies that every connected graph of minimum degree at least three has a dominating set D and a total dominating set T which are disjoint. We show that the Petersen graph is the only such graph for which D∪T necessarily contains all vertices of the graph.

On the computational complexity of (O,P)-partition problems

Jan Kratochvíl, Ingo Schiermeyer (1997)

Discussiones Mathematicae Graph Theory

Similarity:

We prove that for any additive hereditary property P > O, it is NP-hard to decide if a given graph G allows a vertex partition V(G) = A∪B such that G[A] ∈ 𝓞 (i.e., A is independent) and G[B] ∈ P.