The Number of Maximal Independent Sets in the Pm-extended of Graphs

Abstract

A maximal independent set is an independent set that is not a proper subset of any other independent set. Given a graph G of order n, we define the m P -extended of G, denoted G(m), as the graph consisting of G together with n copies of m P , a leaf of each path attached to exactly one vertex of G. In this paper, we determine the number of maximal independent sets of the m P -extended of a star and a path.