两类四角系统的匹配数与点独立集数.PDF

总 32 卷　第 3 期 数　学　研　究 V o l. 32　N o. 3 1999 年 9 月 Jou rnal of M athem atical Study Sep. 1999 两类四角系统的匹配数 与点独立集数① 张 莲 珠 (漳州师范学院数学系, 福建漳州 363000) 摘　要　给出了两类四角系统的完美匹配数、匹配数和点独立集数的计算公式. 关键词　四角系统, 完美匹配数, 匹配数, 点独立集数 设 G = (V , E ) 是一个简单图. M 是E 的子集. 称M 是G 的一个匹配, 如果M 中任意两 条边无公共端点. 匹配亦可看作分支均为K 2 的子图. 若 M = k , 则称M 为k 匹配. 特别地 当k = V (G) 2 时, 称M 为G 的一个完美匹配. G 的完美匹配数用m (G ) 表示. 设A 是V 的 一个子集, 如果A 中的任意两个顶点没有连边, 称A 为点独立集, 若 A = k , 称A 为k 点独立 集. G 的k 匹配数和k 点独立集数分别用 (G ) 和 (G ) 表示, 特别地, (G ) = (G) = 1. G k k 0 0 的匹配总数和点独立集总数分别用( ) ( ) G , G 表示. 即 ( ) ( ) ( ) ( ) G = ∑ i G , G = ∑ i G i 0 i 0 设V ′是V 的一个非空子集, 以V ′为顶点集, 两端点均在V ′中的边的全体为边集所组成的G 的 子图称为G 的由V ′导出子图, 用G [V ] 表示. 设 u 是G 的一个顶点, e 是G 的一条边. 用G - u 表示从G 中删除顶点u 及与u 相关联的边所得到的子图. 用G - e 表示从G 中删除边e 所得 到的子图. 四角系统是一个2 连通平面图, 其每个内部面都是单位正方形. 四角系统的完美匹配与 [ 1, 2 ] 统计晶体物理中的 d im er 问题有关 . 在关四角系统完美匹配的计数参考[4 ]. 这里, 我们考 虑两类四角系统. 设 G 是一个四角系统, 用V 2 表示 G 中的2 度顶点集. 如果G [V V 2 ] 是一条 路, 称G 是含有n 个正方形的锯齿链, 用Z n 表示. 如果G [V V 2 ] 的每个分支是K 2 , 称G 是含有 ( ) n 个正方形的直链. 用L n 表示 图 1 中的粗线表示由V V 2 导出的子图 . 设 e = uv ∈E (G ) , G 的完美匹配数为不含边e 的完美匹配数和含边e 的完美匹配数的和, 即 m (G )