• CONNECTED DOMINATION POLYNOMIAL OF A GRAPH

Abstract

Let G = (V, E) be a simple connected graph of order n. A connected dominating set of G is a set S of vertices of G such that every vertex in V − S is adjacent to some vertex in S and the induced subgraph áSñ is connected. The connected domination number ¡_c(G) is the minimum cardinality of a connected dominating set of G. In this paper we introduce the connected domination polynomial of G. The connected domination polynomial of a connected graph G of order n is the polynomial D_c(G, x) =  where d_c(G, i) is the number of connected dominating set of G of size i and ¡_c(G) is the connected domination number of G. We obtain some basic properties of the connected domination polynomial and compute this polynomial and its roots for some standard graphs.