The upper domatic number of a graph

Abstract

Let be a graph. For two disjoint sets of vertices and , set dominates set if every vertex in is adjacent to at least one vertex in . In this paper we introduce the upper domatic number , which equals the maximum order of a vertex partition such that for every , , either dominates or dominates , or both. We study properties of the upper domatic number of a graph, determine bounds on , and compare to a related parameter, the transitivity of .

Keywords

• domination
• domatic number
• upper domatic number
• transitivity