Domatically critical and domatically full graphs

✍ Scribed by Douglas F. Rall

• Publisher: Elsevier Science
• Year: 1990
• Tongue: English
• Weight: 396 KB
• Volume: 86
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(90)90351-h

✦ Synopsis

A subset, D, of the vertex set of a graph G is called a dominating set of G if each vertex of G is either in D or adjacent to some vertex in D. The maximum cardinality of a partition of the vertex set of G into dominating sets is the domatic number of G, denoted d(G). G is said to be domatically critical if the removal of any edge of G decreases the domatic number, and G is domatically full if d(G) assumes the known lower bound of 6(G) + 1. An example is given to settle a conjecture of B. Zelinka concerning the structure of a domatically critical graph. We also prove that a domatically critical graph G is domatically full if d(G) < 3 and provide' examples to show this does not extend to the cases d(G) > 3.