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