论文部分内容阅读
在组合图论中有一个所谓的“细胞生长”问题,它与动物的发育很类似:从一个特定的正多边形(相当于一个细胞)开始,在平面上一步步向外“生长”,每生长一步即在其外围添加一个相同的细胞且至少有一条边完全重合。如果细胞是一个正方形,则称生成的动物为polyominoes。Polyominoes的研究拥有很悠久的历史,早在20世纪初人们就开始研究它,其中有关数学方面的研究主要集中在覆盖问题、非同构计数问题、匹配计数与排序问题等方面。迄今为止,人们在这些方面已经取得了很多成果。一个polyomino同时也是由方点阵中有限多个以边相连接的正方形的并所组成的一个平面几何图形。在统计物理学中,m×n阶方点阵和m×n阶六角点阵中独立集的计数分别被称为hard四角问题和hard六角问题。
本文我们考虑一类特殊的方点阵——四角链(polyominochain)关于k-匹配数和k-独立集数等参数的极值问题。设Tn表示所有含n个正方形的四角链的集合。对任意四角链Tn∈Tn,分别用mk(Tn)和ik(Tn)表示Tn的k-匹配数和k-独立集数。本文我们证明了对任意四角链Tn∈Tn和任意k≥0,mk(Ln)≥mk(Tn)≥mk(Zn),ik(Ln)≤ik(Tn)≤ik(Zn),且左边的等式对所有k成立当且仅当Tn=Ln,右边的等式对所有k成立当且仅当Tn=An,这里Ln和Zn分别表示线性四角链和锯齿四角链。最后我们分别给出四角链的Hosoya指标(即∑kmk(Tn))和Merrifield-Simmons指标(即∑kik(Tn))的上下界及其递推式。