Independent Vertex Sets in Some Compound Graphs


Ivan Gutman


Let $G$ be an $n$-vertex graph and $R_1,R_2,\dots,R_n$ distinct rooted graphs. The compound graph $G[R_1,R_2,\dots,R_n]$ is obtained by identifying the root of $R_i$ with the $i$-th vertex of $G$, $i=1,2,\dots,n$. We determine the number of independent vertex sets and the independence polynomial of $G[R_1,R_2,\dots,R_n]$. Several special cases of these results are pointed out.