New results on upper domatic number of graphs

Document Type : Original paper

Authors

1 CHRIST (Deemed to be University)

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

Abstract

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.

Keywords

References

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.
Communications in Combinatorics and Optimization
Volume 5, Issue 2
December 2020
Pages 125-137

Files

Share

How to cite

Statistics