Edge-Vertex Dominating Sets and Edge-Vertex Domination Polynomials of Cycles

Abstract

Let G = ( V , E ) be a simple graph. A set S E ( G ) is an edge-vertex dominating set of G (or simply an ev -dominating set), if for all vertices v V ( G ); there exists an edge e S such that e dominates v . Let denote the family of all ev -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 edge-vertex domination polynomial of (or simply an ev -domination polynomial of ) and obtain some properties of this polynomial.