Abstract
Denote by \({\mathcal{T}}_n \) the set of polyomino chains with n squares. For any \(T_n \in \mathcal{T}_n\), let m k (T n ) and i k (T n ) be the number of k-matchings and k-independent sets of T n , respectively. In this paper, we show that for any polyomino chain \( T_n \in \mathcal{T}_n\) and any \(k\geqslant 0\), \(m_{k}(L_n) \geqslant m_{k}(T_n) \geqslant m_{k}(Z_n)\) and \(i_{k}(L_n) \leqslant i_{k}(T_n) \leqslant i_{k}(Z_n)\), with the left equalities holding for all k only if T n =L n , and the right equalities holding for all k only if T n =Z n , where L n and Z n are the linear chain and the zig-zag chain, respectively.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Araujo O., and Rada J. (2001). Matchings in starlike trees. Appl. Math. Lett. 14:843–848
Gutman I., and Zhang F. (1986). On the ordering of graphs with respect to their matching numbers. Discrete Appl. Math. 15: 25–33
Gutman I. (1980). Graphs with greatest number of matchings. Publ. Inst. Math. (Beograd) 27:67–76
Gutman I., and Cvetković D. (1984). Finding tricyclic graphs with maximal number of matchings–Another example of computer aided research in graph theory. Publ. Inst. Math.(Beograd) 35:33–40
Zhang L., and Zhang F. (2000). Extremal hexagonal chains concerning and k-independent sets. J. Math. Chem. 27(4):319–329
Gutman I. (1978). Partial ordering of forests according to their characteristic polynomials. In: Hajnal A., Sós V.T. eds. Combinatorics. North Holland, Amsterdam, pp. 429–436
Gutman I. (1977). Acyclic systems with extremal Hückel π-electron energy. Theory Chim. Acta 45:79–87
Li H. (1999). On minimal energy ordering of acyclic conjugated molecules. J. Math. Chem. 25:145–169
Zhang F., and Li H. (1999). On acyclic conjugated molecules with minimal energies. Discrete Appl. Math. 92:71–84
Engel K. (1990). On the Fivonacci number of an m by n lattice. Fibonacci Quarterly. 28:72–78
Finch S., Several Constants Arising in Statistical Mechanics, http://xxx. lanl. gov/ abs/ math. co/ 9810155.
Baxter R.J., Enting I.G., and Tsang S.K. (1980). Hard Square Lattice Gas. J. Stat. Phys. 22:465–489
Baxter R.J., and Tsang S.K. (1980). Entropy of Hard Hexagons. J. Phys. A. (Math. Gen) 13:1023–1030
Calkin N.J., and Wilf H.S. (1998). The number of independent sets in a grid graph. SIAM J. Discrete Math. 11:54–60
Finch S., Hard Square Entropy Constant, Mathsoft. Inc., http://www. mathsoft. com / asolve/ constant/ square/ square. html.
Zhang F., Li Z., and Wang L. (2001). Hexagonal chains with maximal total π-electron energy. Chem. Phys. Lett. 337: 131–137
Zhang F., Li Z., and Wang L. (2001). Hexagonal chains with minimal total π-electron energy. Chem. Phys. Letters. 337:125–130
Hosoya H. (1971). Topological index. Bull. Chem. Soc. Japan. 44:2332–2339
Farrell E.J. (1979). An introduction to matching polynomials. J. Combin. Theory Ser. B27:75–86
Godsil C.D., and Gutman I. (1979). On the theory of the matching polynomial. J. Graph Theory Ser. B 27:75–86
Gutman I. (1977). The acyclic polynomial of a graph. Publ. Inst. Math. (Beograd) 22:63–69
Merrifield R.E., and Simmons H.E. (1980). The structures of molecular topological-spaces. Theoretica Chimica Acta 55: 55–75
Rada J., and Tieno A. (2003). Polygonal chains with minimal energy. Linear algebra and its applications. 372:333–344
Author information
Authors and Affiliations
Corresponding author
Additional information
This work is supported by NNSFC (10371102).
Rights and permissions
About this article
Cite this article
Zeng, Y., Zhang, F. Extremal Polyomino Chains on k-matchings and k-independent Sets. J Math Chem 42, 125–140 (2007). https://doi.org/10.1007/s10910-005-9039-8
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10910-005-9039-8