Power Dominator Equitable Coloring of Graphs: Bounds and Exact Values for Special Graph Classes

Article Sidebar

PDF
DOI: https://doi.org/10.28924/2291-8639-24-2026-317
Published: Oct 5, 2026
Cite as:
G. Navamani, L. Jacquline, N. Revathi, Lambodharan Velappan, V. Kolappan, Power Dominator Equitable Coloring of Graphs: Bounds and Exact Values for Special Graph Classes, Int. J. Anal. Appl., 24 (2026), 317.

Main Article Content

G. Navamani, L. Jacquline, N. Revathi, Lambodharan Velappan, V. Kolappan

Abstract

This paper introduces the concept of the power dominator equitable coloring, which combines the monitoring capability of power dominator coloring with the balanced partition requirement of equitable coloring. A proper coloring is called a power dominator equitable coloring if every vertex power dominates at least one color class and the sizes of any two color classes differ by at most one. The minimum number of colors required for such a coloring is called the power dominator equitable chromatic number and is denoted by \(\chi_{pde} (G)\). We establish several fundamental bounds for this new parameter and characterize graphs attaining equality. Exact values are obtained for complete multipartite graphs, disconnected graphs, forests and circulant graphs \(C_n (1,2)\). In addition, relationships between the power dominator equitable chromatic number and the equitable chromatic number are investigated, together with sufficient conditions under which they coincide. These results provide a theoretical foundation for studying graph coloring problems involving both monitoring capability and balanced resource allocation.

Article Details

References

  1. M. Borbényi, P. Csikvári, H. Luo, On the Number of Forests and Connected Spanning Subgraphs, Graphs Comb. 37 (2021), 2655–2678. https://doi.org/10.1007/s00373-021-02382-x.
  2. M. Chellali, F. Maffray, Dominator Colorings in Some Classes of Graphs, Graphs Comb. 28 (2012), 97–107. https://doi.org/10.1007/s00373-010-1012-z.
  3. B.L. Chen, K.W. Lih, Equitable Coloring of Trees, J. Comb. Theory Ser. B 61 (1994), 83–87. https://doi.org/10.1006/jctb.1994.1032.
  4. M. Zhao, L. Kang, G.J. Chang, Power Domination in Graphs, Discrete Math. 306 (2006), 1812–1816. https://doi.org/10.1016/j.disc.2006.03.037.
  5. P. Dorbec, M. Mollard, S. Klavžar, S. Špacapan, Power Domination in Product Graphs, SIAM J. Discrete Math. 22 (2008), 554–567. https://doi.org/10.1137/060661879.
  6. R. Gera, On the Dominator Colorings in Bipartite Graphs, in: Fourth International Conference on Information Technology (ITNG'07), IEEE, 2007, pp. 947–952. https://doi.org/10.1109/ITNG.2007.142.
  7. F. Harary, A.J. Schwenk, The Number of Caterpillars, Discrete Math. 6 (1973), 359–365. https://doi.org/10.1016/0012-365X(73)90067-8.
  8. T.W. Haynes, S.M. Hedetniemi, S.T. Hedetniemi, M.A. Henning, Domination in Graphs Applied to Electric Power Networks, SIAM J. Discrete Math. 15 (2002), 519–529. https://doi.org/10.1137/S0895480100375831.
  9. T.W. Haynes, S.T. Hedetniemi, M.A. Henning, Domination in Graphs: Core Concepts, Springer International Publishing, 2023. https://doi.org/10.1007/978-3-031-09496-5.
  10. C. Heuberger, On Planarity and Colorability of Circulant Graphs, Discrete Math. 268 (2003), 153–169. https://doi.org/10.1016/S0012-365X(02)00685-4.
  11. H.A. Kierstead, A.V. Kostochka, A Short Proof of the Hajnal–Szemerédi Theorem on Equitable Colouring, Combin. Probab. Comput. 17 (2008), 265–270. https://doi.org/10.1017/S0963548307008619.
  12. K.M. Koh, K.W. Soh, On the Power Domination Number of the Cartesian Product of Graphs, AKCE Int. J. Graphs Comb. 16 (2019), 253–257. https://doi.org/10.1016/j.akcej.2019.02.004.
  13. P.C.B. Lam, W.C. Shiu, C.S. Tong, Z.F. Zhang, On the Equitable Chromatic Number of Complete n-Partite Graphs, Discrete Appl. Math. 113 (2001), 307–310. https://doi.org/10.1016/S0166-218X(00)00296-1.
  14. E. Malaguti, P. Toth, A Survey on Vertex Coloring Problems, Int. Trans. Oper. Res. 17 (2010), 1–34. https://doi.org/10.1111/j.1475-3995.2009.00696.x.
  15. W. Meyer, Equitable Coloring, Am. Math. Mon. 80 (1973), 920–922. https://doi.org/10.1080/00029890.1973.11993408.
  16. G. Navamani, L. Jacquline, Power Dominator Equitable Coloring for Some Standard Graphs, Commun. Appl. Nonlinear Anal. 32 (2025), 529–534. https://doi.org/10.52783/cana.v32.3316.
  17. K. Sathish Kumar, N. Gnanamalar David, A.K. Nagar, G. Subramaninan, Power Dominator Chromatic Numbers of Splitting Graphs of Certain Classes of Graphs, Commun. Comb. Optim. 9 (2024), 317–327. https://doi.org/10.22049/cco.2023.27744.1337.
  18. M. Shukla, F. Chandarana, Dominator Coloring of Total Graph of Path and Cycle, Math. Model. Eng. 9 (2023), 72–80. https://doi.org/10.21595/mme.2023.23228.
  19. A. Uma Maheswari, J. Bala Samuvel, Power Dominator Chromatic Number for Some Special Graphs, Int. J. Innov. Technol. Explor. Eng. 8 (2019), 3957–3960. https://doi.org/10.35940/ijitee.L3466.1081219.