APP下载

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是一个……

登录APP查看全文

猜你喜欢

定义
活用定义巧解统计概率解答题
例谈椭圆的定义及其应用
题在书外 根在书中——圆锥曲线第三定义在教材和高考中的渗透
永远不要用“起点”定义自己
严昊:不定义终点 一直在路上
定义“风格”
成功的定义
有壹手——重新定义快修连锁
修辞学的重大定义
山的定义