Domination Polynomials for Inverse Graphs

International Journal of Mathematics Trends and Technology (IJMTT)
© 2022 by IJMTT Journal
Volume-68 Issue-6
Year of Publication : 2022
Authors : J. Baskar Babujee, Temesgen Engida Yimer

How to Cite?

J. Baskar Babujee, Temesgen Engida Yimer, "Domination Polynomials for Inverse Graphs," International Journal of Mathematics Trends and Technology, vol. 68, no. 6, pp. 1-7, 2022. Crossref,

Let G = (V, E) be a simple undirected graph with order n. The inverse, or complement, of a graph G is denoted by G- and is obtained by filling in all the remaining edges needed to form a complete graph while removing all previously existing edges. Equivalently, V(G) = V(G-) and E(G-) = E(Kn) - E(G) and also | E(G-)| = (n/2) - |E(G)|. A domination polynomial of an inverse graph of G is given as D(G-,x) = Σni=γ(G) d(G-,x)xi, where d(G-,x) is the number of all dominating sets of G- with size i and γ(G-) is the minimum domination number of G-. In this paper, we introduce a generating function called a domination polynomial for inverse dominating sets of cycle, star, wheel graphs, and triangular book graphs. Also, the bounds of the minimum dominating number γ(G) discussed with their corresponding inverse of the minimum dominating number γ(G-).

Keywords : Dominating set, Domination polynomials, Inverse of graph.


[1] Akbari, S. Alikhani and Y.H. Peng YH, Characterization of Graphs using Domination Polynomials, European J. Combin, 31(2010) 1714–1724.
[2] S. Alikhani and Y.H. Peng, Dominating sets and Domination Polynomials of paths, Int. J. Math. Sci, 10(2009)1–10.
[3] S. Alikhani and Y.H. Peng, Introduction to Domination Polynomial of a Graph, Ars Combin,114 (2014)257–266.
[4] J.L. Arocha and B.Llano, Mean Value for the Matching and Dominating Polynomial, Discussiones Mathematicae Graph Theory, 20(1)(2000)57–70
[5] T.W. Haynes, S.T. Hedetniemi and P.J. Sater. Fundamentals of Domination of Graphs, Marcel Dekker, Inc, NewYork, (1989).
[6] T.W. Haynes, S.T. Hedetniemi and P.J. Sater. Domination in Graphs:Advanced Topics, Marcel Dekker, Inc, NewYork, (1998).
[7] T. Kotek , J. Preen and P. Tittmann. Domination polynomials of graphs products, arXiv:305.1475v2[math.CO] (2013).
[8] P.S. Nair . Construction of self-complementary graphs, Discrete Math, 175 (1997) 283–287.
[9] J. Peterson . Die Theorie der regularen Graphs, Acta Mathematica, 15(1) (1891)193-220.
[10] N.B. Rathod and K.K. Kanani. k-cordial Labeling of Triangular Book, Triangular Book with Book Mark and Jewel Graph, Global Journal of Pure and Applied Mathematics, 13(10) (2017) 6979–6989.
[11] J.J. Sylvester . On an application of the New Atomic Theory to the Graphical Presentation of the Invariants and Covariant Of Binary Quantic, American Journal of Mathematics, 1 (1878) 161-228.
[12] Wyatt J, Desormeaux, and T.W. Haynes . Domination parameters of a graph and its complement, Discussiones mathematicae graph theory, 38 (2018)203–215.
[13] T.E. Yimer and J. Baskar Babujee . Perfect Domination Polynomial of a Homogeneous Caterpillar Graph and Full Binary Tree, Mathematical Notes,111(2) (2022) 129–136.
[14] T.E. Yimer and J. Baskar Babujee. Domination polynomial of a corona graph, IOSR Journal of Mathematics; 18(2) (2022) 47–51