Back
 OJDM  Vol.3 No.1 , January 2013
Dominating Sets and Domination Polynomials of Square of Paths
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.
Cite this paper: A. Vijayan and K. Gipson, "Dominating Sets and Domination Polynomials of Square of Paths," Open Journal of Discrete Mathematics, Vol. 3 No. 1, 2013, pp. 60-69. doi: 10.4236/ojdm.2013.31013.
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.

 
 
Top