Comparative Analysis of the Domination Polynomial and the Independent Domination Polynomial of Graphs

Abstract

In this paper, we study and analyze two important polynomials in graph theory, namely the domination polynomial  and the independent domination polynomial   We first show that for any simple graph G and any integer i, the corresponding coefficient in the independent domination polynomial is always less than or equal to that in the domination polynomial; that is . A necessary and sufficient condition for the equality   is also provided, according to which equality holds if and only if every ii-element dominating set of the graph is independent. Subsequently, the behavior of the coefficients of these two polynomials and their differences is thoroughly analyzed for classical families of graphs, including paths, cycles, complete graphs, and stars. The obtained results indicate that the independence constraint plays a fundamental role in reducing the number of dominating sets, and the difference between the coefficients of the two polynomials is highly dependent on the structure of the graph. This study provides an analytical framework for comparing domination polynomials and their generalizations based on structural constraints.