Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: Vertex partition

Sortuj według:

Ogranicz wyniki do:

Graphs with disjoint dominating and paired-dominating sets

100%

Southey J., Henning M.

Open Mathematics

2010

tom 8

nr 3

459-467

A dominating set of a graph is a set of vertices such that every vertex not in the set is adjacent to a vertex in the set, while a paired-dominating set of a graph is a dominating set such that the subgraph induced by the dominating set contains a perfect matching. In this paper, we show that no minimum degree is sufficient to guarantee the existence of a disjoint dominating set and a paired-dominating set. However, we prove that the vertex set of every cubic graph can be partitioned into a dominating set and a paired-dominating set.

Dominating and total dominating partitions in cubic graphs

100%

Southey J., Henning M.

Open Mathematics

2011

tom 9

nr 3

699-708

In this paper, we continue the study of domination and total domination in cubic graphs. It is known [Henning M.A., Southey J., A note on graphs with disjoint dominating and total dominating sets, Ars Combin., 2008, 89, 159–162] that every cubic graph has a dominating set and a total dominating set which are disjoint. In this paper we show that every connected cubic graph on nvertices has a total dominating set whose complement contains a dominating set such that the cardinality of the total dominating set is at most (n+2)/2, and this bound is essentially best possible.

Ograniczanie wyników

2 Open Mathematics

2 Henning M.

2 Southey J.

1 2011

1 2010

Wyniki wyszukiwania

Graphs with disjoint dominating and paired-dominating sets

Dominating and total dominating partitions in cubic graphs