On graphs with disjoint dominating and 2-dominating sets | Zendy

Michael A. Henning | Zendy; Douglas F. Rall | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

On graphs with disjoint dominating and 2-dominating sets

Author(s) -

Michael A. Henning,

Douglas F. Rall

Publication year - 2012

Publication title -

discussiones mathematicae graph theory

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.476

H-Index - 19

eISSN - 2083-5892

pISSN - 1234-3099

DOI - 10.7151/dmgt.1652

Subject(s) - combinatorics , mathematics , dominating set , disjoint sets , graph , discrete mathematics , constructive , computer science , vertex (graph theory) , process (computing) , operating system

A DD2-pair of a graph G is a pair (D,D2) of disjoint sets of vertices of G such that D is a dominating set and D2 is a 2-dominating set of G. Although there are infinitely many graphs that do not contain a DD2-pair, we show that every graph with minimum degree at least two has a DD2-pair. We provide a constructive characterization of trees that have a DD2-pair and show that K3,3 is the only connected graph with minimum degree at least three for which D ∪ D2 necessarily contains all vertices of the graph.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research