Abstract

Let G = (V, E) be a simple Graph. A set S  V(G) is a vertex-edge dominating set (or simplyve-dominating set) if for all edges e  E(G), there exist a vertex v  S such that v dominates e. In this paper, we study the concept of vertex-edge domination polynomial of the path Pn. The vertex-edge domination polynomial of Pn is Dve, where dve(Pn, i) is the number of vertex edge dominating sets of Pn with cardinality i. We obtain some properties of Dve(Pn, x) and its co-efficients. Also, we calculate the recursive formula to derive the vertex-edge domination polynomials of paths.

Keywords

References

[1] G. Chartrand and P. Zhang, Introduction to Graph theory, McGraw-Hill, Boston, Mass, USA, 2005.
[2] J.A. Bondy and U.S.R. Murty, Graph theory with Applications, Elsevier science publishing co, sixth printing, 1984.
[3] S. Alikhani and Y.H. Peng, Domination sets and Domination polynomials of cycles, Global Journal of pure and Applied Mathematics vol.4 no.2, 2008.
[4] S. Alikhani and Y.H. Peng, Dominating sets and Domination polynomials of paths, International journal of Mathematics and mathematical sciences, 2009.
[5] S. Alikhani and Y.H. Peng, Introduction to Domination polynomial of a graph, arXiv : 0905.225 [v] [math.co] 14 may, 2009.
[6] T.W. Haynes, S.T. Hedetniemi, P.J. Slater. Fundamentals of Domination in Graphs, Marcel Dekker, Newyork, 1998.