Extremal Polyphenyl Spiders Concerning \(k\)-matchings and \(k\)-independent Sets

Abstract

Denote by \(\mathcal{P}(n_1, n_2, n_3)\) the set of all polyphenyl spiders with three legs of lengths \(n_1\), \(n_2\), and \(n_3\). Let \(S^j(n_1, n_2, n_3) \in \mathcal{P}(n_1, n_2, n_3)\) (\(j \in \{1, 2, 3\}\)) be three non-isomorphic polyphenyl spiders with three legs of lengths \(n_1\), \(n_2\), and \(n_3\), and let \(m_k(G)\) and \(i_k(G)\) be the numbers of \(k\)-matchings and \(k\)-independent sets of a graph \(G\), respectively. In this paper, we show that for any \(S^j(n_1, n_2, n_3) \in \mathcal{P}(n_1, n_2, n_3)\) (\(j \in \{1, 2, 3\}\)), we have \(m_k(S_M^3(n_1, n_2, n_3)) \leq m_k(S^j(n_1, n_2, n_3)) \leq m_k(S^j(n_1, n_2, n_3))\) and \(i_k(S_O^1(n_1, n_2, n_3)) \leq i_k(S^j(n_1, n_2, n_3)) \leq i_k(S^3_M(n_1, n_2, n_3))\), with equalities if and only if \(S^j(n_1, n_2, n_3) = S_M^3(n_1, n_2, n_3)\) or \(S^j(n_1, n_2, n_3) = S_O^1(n_1, n_2, n_3)\), where \(S_O^1(n_1, n_2, n_3)\) and \(S_M^3(n_1, n_2, n_3)\) are respectively an ortho-polyphenyl spider and a meta-polyphenyl spider.