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→B, if for every vertex u∈B there exists a vertex v∈A such that uv∈E(G). For any graph G, a partition π={V1, V2, …, Vp} of the vertex set V is an \textit{upper domatic partition} if Vi→Vj or Vj→Vi or both for every Vi,Vj∈π, whenever i≠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 kth 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