The upper domatic number of powers of graphs

Document Type : Original paper

Authors

1 CHRIST (Deemed to be University), Bangalore

2 CHRIST(Deemed to be University), Bangalore

Abstract

Let $A$ and $B$ be two disjoint subsets of the vertex set $V$ of a graph $G$. The set $A$ is said to dominate $B$, denoted by $A \rightarrow B$, if for every vertex $u \in B$ there exists a vertex $v \in A$ such that $uv \in E(G)$. For any graph $G$, a partition $\pi = \{V_1,$ $V_2,$ $\ldots,$ $V_p\}$ of the vertex set $V$ is an \textit{upper domatic partition} if $V_i \rightarrow V_j$ or $V_j \rightarrow V_i$ or both for every $V_i, V_j \in \pi$, whenever $i \neq j$. The \textit{upper domatic number} $D(G)$ is the maximum order of an upper domatic partition. In this paper, we study the upper domatic number of powers of graphs and examine the special case when power is $2$. We also show that the upper domatic number of $k^{\mathrm{th}}$ power of a graph can be viewed as its $ k$-upper domatic number.

Keywords

Main Subjects

References

[1] E. J. Cockayne and S. T. Hedetniemi, Towards a theory of domination in graphs, Networks 7 (1977), no. 3, 247–261.
[2] P. Francis and S. F. Raj, On b-coloring of powers of hypercubes, Discrete Appl. Math. 225 (2017), no. 10, 74–86.
[3] F. Harary, Graph Theory, Addison- Wesley Publishing Company, Inc, 1969.
[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. 17 (2020), no. 1, 139–148.
[5] S. T. Hedetniemi, P. Slater, and T. W. Haynes, Fundamentals of Domination in Graphs, CRC Press, 1998.
[6] L. C. Samuel and M. Joseph, New results on upper domatic number of graphs, Commun. Comb. Optim. 5 (2020), no. 2, 125–137.
[7] D. B. West, Introduction to Graph Theory, Prentice Hall, 1996.
 
Communications in Combinatorics and Optimization
Volume 6, Issue 1
June 2021
Pages 53-65

Files

Share

How to cite

Statistics