Let  be a simple graph. Then a dominating set D is a certified dominating set of G if every vertex  has either zero or at least two neighbours in  Let  be the complete bipartite graph with vertices and let denote the family of certified dominating sets of  with cardinality i. Let  Then in this paper, we obtain a exact formula for  Using this formula, we construct the certified domination polynomial

and obtain some properties of this polynomial.

domination, certified domination, certified domination number, certified dominating set and certified domination polynomial.

Received: November 4, 2024; Revised: November 29, 2024; Accepted: December 17, 2024; Published: February 15, 2025

How to cite this article: K. Lal Gipson and M. J. Angelin Jenisha, Certified dominating sets and certified domination polynomial of complete bipartite graph  Advances and Applications in Discrete Mathematics 42(3) (2025), 273-283. https://doi.org/10.17654/0974165825018

This Open Access Article is Licensed under Creative Commons Attribution 4.0 International License

References:
[1] A. M. Anto and P. Paul Hawkins, Perfect dominating sets and perfect domination polynomial of some standard graphs, Turkish Journal of Computer and Mathematics Education 11(3) (2020), 1178-1182.
[2] S. Chandrasekaran and K. Kanimozhi, Perfect domination polynomial for lollipop graph IOSR Journal of Engineering 9(1) (2019), 72-76.
[3] Jyoti Rani and Seema Mehra, Total domination polynomial of some graphs, Advances and Applications in Discrete Mathamatics 25(2) (2020), 161-171. http://dx.doi.org/10.17654/DM025020161
[4] K. Lal Gipson and S. Arun Williams, 2-edge dominating sets and 2-edge domination polynomials of paths, Malaya Journal of Matematik 9(1) (2021), 844 849.
[5] K. Lal Gipson and T. Subha, Secure dominating sets and secure domination polynomials of centipedes, Journal of Xi’an Shiyan University, Natural Science Edition, 18(3) (2022), 36-40.
[6] Magda Dettlaf, Magdalena Lemanska, Jerzy Topp, Radoslaw Ziemann and Pawel Zylinski, Certified domination, AKCE International Journal of Graphs and Combinatorics 17(1) (2020), 86-97.
[7] Nechrivan B. Ibrahim and Assad A. Jund, Edge connected domination polynomial of a graph, Palestine Journal of Mathamatics 7(2) (2018), 458-467.
[8] P. Paul Hawkins, A. M. Anto and T. Shyla Issac Mary, Perfect dominating sets and perfect domination polynomial of a star graph, Malaya Journal of Matematik 8(4) (2020), 1751-1755.
[9] Sahib Shayyal Kahat, Abdul Jalil M. Khalaf and Roslan Hasni, Dominating sets and domination polynomials of stars, Australian Journal of Basic and Applied Sciences 8(6) (2014), 383-386.
[10] Sahib Sh. Kahat, Abdul Jalil M. Khalaf and Roslan Hasni, Dominating sets and domination polynomial of wheels, Asian Journal of Applied Sciences 2(3) (2014), 287-290.
[11] Y. A. Shiny and Anitha Baby, Connected 2-dominating sets and connected 2- domination polynomial of the complete bipartite graph Ratio Mathematics 44 (2022), 51-55.
[12] Dr. A. Vijayan and Felix Nes Mabel, Connected domination polynomial of some graphs, IOSR Journal of Mathematics 12(4) Ver III (2016), 13-16.
[13] A. Vijayan and K. Lal Gipson, Dominating sets and domination polynomials of square of paths, Open Journal of Discrete Mathematics 3 (2013), 60-69.