Domination Polynomials for Inverse Graphs

J. Baskar Babujee; Temesgen Engida Yimer

doi:https://doi.org/10.14445/22315373/IJMTT-V68I6P501

International Journal of Mathematics Trends and Technology

Research Article | Open Access | Download PDF

Volume 68 | Issue 6 | Year 2022 | Article Id. IJMTT-V68I6P501 | DOI : https://doi.org/10.14445/22315373/IJMTT-V68I6P501

Domination Polynomials for Inverse Graphs

J. Baskar Babujee, Temesgen Engida Yimer

Received	Revised	Accepted	Published
04 Apr 2022	23 May 2022	02 Jun 2022	12 Jun 2022

Citation :

J. Baskar Babujee, Temesgen Engida Yimer, "Domination Polynomials for Inverse Graphs," International Journal of Mathematics Trends and Technology (IJMTT), vol. 68, no. 6, pp. 1-7, 2022. Crossref, https://doi.org/10.14445/22315373/IJMTT-V68I6P501

Abstract

Let 𝐺 = (𝑉, 𝐸) be a simple undirected graph with order n. The inverse, or complement, of a graph 𝐺 is denoted by 𝐺̅and is obtained by filling in all the remaining edges needed to form a complete graph while removing all previously existing edges. Equivalently, 𝑉 (𝐺) = 𝑉 (𝐺̅) and E(𝐺̅) = E(Kn) − E(G) and also |𝐸(𝐺̅)| = ( 𝑛 2 ) − |𝐸(𝐺)|. A domination polynomial of an inverse graph of G is given as 𝐷(𝐺̅, 𝑥 ) = ∑ 𝑑(𝐺̅, 𝑥 )𝑥 𝑛 𝑖 𝑖=𝛾(𝐺̅) , where 𝑑(𝐺̅, 𝑥 ) is the number of all dominating sets of 𝐺̅with size 𝑖 and γ(𝐺̅) is the minimum domination number of 𝐺̅. 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 γ(𝐺̅).

Keywords

Dominating set, Domination polynomials, Inverse of graph.

References

[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.