Dominating Sets and Domination Polynomials of Square of Paths

A. Vijayan, K. Lal Gipson

Department of Mathematics, Mar Ephraem College of Engineering and Technology, Kanayakumari District, India.
Department of Mathematics, Nesamony Memorial Christian College, Marthandam, India.

DOI: 10.4236/ojdm.2013.31013                

Abstract

Let G = (V, E) be a simple graph. A set S í V is a dominating set of G, if every vertex in V-S is adjacent to at least one vertex in S. Let be the square of the Path and let denote the family of all dominating sets of with cardinality i. Let . In this paper, we obtain a recursive formula for . Using this recursive formula, we construct the polynomial, , which we call domination polynomial of and obtain some properties of this polynomial.

Keywords

Domination Set; Domination Number; Domination Polynomials

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	S. Alikhani and Y.-H. Peng, “Introduction to Domination Polynomial of a Graph,” .arXiv:0905.2251v1[math.co], 2009.
[2]	S. Alikhani and Y.-H. Peng, “Domination Sets and Domination Polynomials of Paths,” International Journal of Mathematics and Mathematical Sciences, Vol. 2009, 2009, Article ID: 542040.
[3]	G. Chartand and P. Zhang, “Introduction to Graph Theory,” McGraw-Hill, Boston, 2005.