New results on upper domatic number of graphs

Document Type : Original paper


1 CHRIST (Deemed to be University)

2 CHRIST(Deemed to be University) Hosur Road Bangalore-560029


For a graph $G = (V, E)$, a partition $\pi = \{V_1,$ $V_2,$ $\ldots,$ $V_k\}$ of the vertex set $V$ is an \textit{upper domatic partition} if $V_i$ dominates $V_j$ or $V_j$ dominates $V_i$ or both for every $V_i, V_j \in \pi$, whenever $i \neq j$. The upper domatic number $D(G)$ is the maximum order of an upper domatic partition of $G$. We study the properties of upper domatic number and propose an upper bound in terms of clique number. Further, we discuss the upper domatic number of certain graph classes including unicyclic graphs and power graphs of paths and cycles.


1] E. J. Cockayne and S. T. Hedetniemi, Towards a theory of domination in graphs, Networks 7 (1977), no. 3, 247–261.
[2] F. Harary, Graph theory, Addison-Wesley Publishing Company, Inc, 1969.
[3] T. W. Haynes, J. T. Hedetniemi, S. T. Hedetniemi, and A. McRae, The transitivity of special graph classes, J. Combin. Math. Combin. Comput. (In press) (2017).
[4] T. W. Haynes, J. T. Hedetniemi, S. T. Hedetniemi, A. McRae, and N. Phillips, The upper domatic number of a graph, AKCE Int. J. Graphs Comb. (In press) (2018).
[5] J. T. Hedetniemi and S. T. Hedetniemi, The transitivity of a graph, J. Combin. Math. Combin. Comput. 104 (2018), 75–91.