一类特殊立方图的完美匹配个数
杨春侠广东工业大学华立学院公共基础部
【摘要】一个立方图是一个所有顶点都是三度点的图，边集E（G）的子集M称为G的一个完美匹配，若其中的每个元素为边且任意两个在G中不相邻，并满足|V（M）|＝|V（G）|。
【关键词】立方图完美匹配
【中图分类号】O13【文献标识码】A【文章编号】1006－9682（2009）03－0137－01
【Abstract】Acubicgraphisagrapheachvertexofwhichhasdegreethree.AsubsetMofE（G）iscalledaperfectmatchinginGifitselementsarelinksandnotwoareadjacentinGand|V（M）|＝|V（G）|.
【Keywords】CubicgraphPerfectmatching
定理1，若立方图G的每个块均为k4－e，则pm（G）＝1＋2k，其中k（k≥2）是G中k4－e的个数。
证明：若G为立方图，且G的每个块均为k4－e，而每个k4－e均有两个2度点。故G可看作由k4－e作为点构成的一个圈。由G的结构易知：圈上的边或者全在G的完美匹配之中，或者全部不在G的完美匹配之中。
当G的完美匹配包含圈上的边时，显然每个k4－e对完美匹配的个数贡献为1，故只有1个此类的完美匹配。
当G的完美匹配不包含圈上的边时，则此类完美匹配全部由k4－e上的边构成，此时每个k4－e对完美匹配的个数贡献为2，故有2k个此类的完美匹配。
所以pm（G）＝1＋2k。
定理2，若立方图G的每个块均为梭子，则pm（G）＝2k＋1，其中k（k≥2）是G中梭子的个数。
证明：若G为立方图，且G的每个块均为梭子，而每个梭子均有两个2度点。故G可看作由梭子作为点构成的一个圈。如图2所示：
由G的结构易知：圈上的边或者全在G的完美匹配之中，或者全部不在G的完美匹配之中。
当G的完美匹配包含圈上的边时，显然每个梭子对完美匹配的个数贡献为2，故有2k个此类的完美匹配。
当G的完美匹配不包含圈上的边时，则此类完美匹配全部由梭子上的边构成，此时每个梭子对完美匹配的个数贡献为2，故亦有2k个此类的完美匹配。
所以pm（G）＝2k＋2k＝2k＋1。
定理3，若立方图G的块均为梭子和k4－e，则pm（G）＝2s（1＋2k），其中k（k≥1）是G中k4－e的个数，s（s≥1）是G中梭子的个数。
证明：因为G为立方图，且G的每个块均为梭子或者k4－e，而每个梭子和k4－e均有两个2度点。故G可看作由梭子和k4－e作为点构成的一个圈。由G的结构易知：圈上的边或者全在G的完美匹配之中，或者全部不在G的完美匹配之中。
当G的完美匹配包含圈上的边时，显然每个k4－e对完美匹配的个数贡献为1，每个梭子对完美匹配的个数贡献为2，故有2s个此类的完美匹配。
当G的完美匹配不包含圈上的边时，则此类完美匹配全部由梭子和k4－e上的边构成，此时每个梭子和每个k4－e对完美匹配的个数贡献都为2，故有2k+s个此类的完美匹配。
所以pm（G）＝2s＋2k+s＝2s（1＋2k）。
参考文献
1J.A.BondyandU.S.R.Murty,《GraphTheorywithApplications》,
MacmillanPress,London,1976