×

Extremal polyphenyl chains concerning \(k\)-matchings and \(k\)-independent sets. (English) Zbl 1247.92065

Summary: 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. Let \(M_n\) and \(O_n\) are the meta-chain and the ortho-chain, respectively. 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)\) and \(i_k(M_n)\geq i_k(A_n)\geq i_k(O_n)\), where the equalities hold only if \(A_n=M_n\) or \(A_n=O_n\). These generalize some related results in Y. Bai, B. Zhao and P. Zhao [MATCH Commun. Math. Comput. Chem. 62, No. 3, 649–656 (2009; Zbl 1274.05087)].

MSC:

92E10 Molecular structure (graph-theoretic methods, methods of differential topology, etc.)
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C90 Applications of graph theory
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

Citations:

Zbl 1274.05087
PDFBibTeX XMLCite