M2-等可覆盖图的一个注记
2011-06-05张玉琴姜雪娇
张玉琴,姜雪娇
(天津大学理学院,天津 300072)
M2-等可覆盖图的一个注记
张玉琴,姜雪娇
(天津大学理学院,天津 300072)
图的覆盖问题是图论研究的一个主要内容.若图G的每个极小H-覆盖都是它的最小H-覆盖,则称图G为H-等可覆盖的.为刻画2M-等可覆盖图的特征,采用分类讨论的方法,得出2M-等可覆盖图的一个重要结果:若连通图G含6圈,则G不是2M-等可覆盖的.这为2M-等可覆盖图的完全刻画奠定了有力的基础.
H-覆盖;H-等可覆盖图;圈
图的覆盖问题是图论研究的一个主要内容,具有重要的理论意义与实际意义.H-等可覆盖图的刻画问题起源于对H-可分解图,随机H-可填充图及H-等可填充图见文献[1-8]的研究.文献[9]完全刻画了P3-等可覆盖图的特征,文献[10]刻画了一些特殊的M2-等可覆盖图.笔者考虑的图都是有限且没有孤立结点的简单图.图G的阶数为V(G),边数为E(G).k个结点的圈用Ck表示.设M是边集E(G)的一个子集,如果M中任何2条边都不相邻,则称M是G的一个匹配.用Mt(t≥1)来表示t条边的匹配.设e∈E(G),称G中与e不相邻的边数为e的边不邻度.
1 预备知识
首先给出文中需要的重要定义和已知结论.
定义1 设图H为图G的一个子图,H1,H2,…,Hk为同构于H的G的子图.若G的每条边至少出现在一个Hi(i=1,2,…,k )中,则{H1,H2,…,Hk}称为G的一个H-覆盖.
定义2 设H1,H2,…,Hk为G的一个H-覆盖.若对于任意Hj,j∈{1,2,…,k} ,)−E(Hj)都不是G的一个覆盖,则称{H1,H2,…,Hk}为G的一个极小覆盖.
定义3 若不存在少于k个同构于H的子图可覆盖G,则称{H1,H2,…,Hk}为G的最小H-覆盖.
定义4 若G的每个极小H-覆盖都是它的最小H-覆盖,则称G为H-等可覆盖的.
例如,圈C5是一个……
