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.
Citation Information
Haynes, Teresa W.; and Henning, Michael A.. 2000. The Domatic Numbers of Factors of Graphs. Ars Combinatoria. Vol.56 161-173. https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.357.3317&rep=rep1&type=pdf ISSN: 0381-7032