On Connectivity Polynomial of Graphs

In this paper we introduce a new graph polynomial, say connectivity polynomial. Let [Formula: see text] be a simple graph of order [Formula: see text]. The connectivity polynomial of [Formula: see text], denoted by [Formula: see text], is [Formula: see text], where [Formula: see text] and [Formula: see text] (for [Formula: see text]) is the number of connected induced subgraphs of [Formula: see text] with order [Formula: see text]. We investigate some properties of the connectivity polynomial. We find the connectivity polynomial of disjoint union and join of graphs. Finally, we find the coefficients of this polynomial in terms of the vertex connectivity and the order of graphs.