On the domination polynomials of non P4-free graphs
Saeid Alikhani · 2013
Abstract. A graph G is called P4-free, if G does not contain an induced subgraph P4. The domination polynomial of a graph G of order n is the polynomial D(G,x) = n i=1 d(G, i)xi, where d(G, i) is the number of dominating sets of G of size i. Every root ofD(G, x) is called a domination root of G. In this paper we state and prove formula for the domination polynomial of non P4-free graphs. Also, we pose a conjecture about domination roots of these kind of graphs.