Extremal Polyphenyl Chains Concerning \(k\)-Matchings and \(k\)-Independent Sets

Abstract

Denote by \(\mathcal{A_n}\), the set of the polyphenyl chains with \(n\) hexagons. For any \(A_n \in \mathcal{A_n}\), let \(m_k(A_n)\) and \(i_k(A_n)\) be the numbers of \(k\)-matchings and \(k\)-independent sets of \(A_n\), respectively. In the paper, we show that for any \(A_n \in \mathcal{A_n}\) and for any \(k \geq 0\),\(m_k(M_n) \leq m_k(A_n) \leq m_k(O_n) \quad \text{and} \quad i_k(M_n) \geq i_k(A_n) \geq i_k(O_n),\) with the equalities holding if \(A_n = M_n\) or \(A_n = O_n\), where \(M_n\) and \(O_n\) are the meta-chain and the ortho-chain, respectively. These generalize some related results in \([1]\).