Dominating Sets and Domination Polynomials of Square of Paths


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.

Share and Cite:

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.

Conflicts of Interest

The authors declare no conflicts of interest.


[1] S. Alikhani and Y.-H. Peng, “Introduction to Domination Polynomial of a Graph,” .arXiv:0905.2251v1[], 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.

Copyright © 2020 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.