The Domatic Numbers of Factors of Graphs

Document Type

Article

Publication Date

7-1-2000

Description

The maximum cardinality of a partition of the vertex set of a graph G into dominating sets is the domatic number of G, denoted d(G). We consider Nordhaus-Gaddum type results involving the domatic number of a graph, where a Nordhaus-Gaddum type result is a (tight) lower or upper bound on the sum or product of a parameter of a graph and its complement. Thereafter we investigate the upper bounds on the sum and product of the domatic numbers d(G1), d(G2) and d(G3) where G1⊕G2⊕G3 = Kn. We show that the upper bound on the sum is n + 2, while the maximum value of the product is ⌊n/3⌋3 for n ≥ 57.

Share

COinS