{nest,gap}-free图的边理想正则度的研究

杨 娟，刘阿明

（海南大学 理学院，海南 海口 570228）

文中所涉及的图都是连通的简单图，且不含有孤立点.记简单图G=｛V，E｝，其中V=｛x1，x2，…，xn｝是图G的顶点集，E=｛xixj|xi，xj在G中相邻｝是图G的边集.设u，v∈V（G），如果uv∈E（G），则记uv∈G为图G的一条边.假设H是简单图，若图G不含H作为导出子图，则称G是H-free图.设R=K［x1，x2，…，xn］是k域上的n元多项式环.图G的边理想为：I（G）=＜xixj|｛xi，xj｝∈E（G）＞.

Fröberg［1］首先给出了所有正则度为2的简单图的经典刻画，即对简单图G，图G的正则度reg（I（G））=2当且仅当Gc是弦图，其中reg（I（G））表示边理想I（G）的Castelnuovo-Mumford 正则度.Francisco-Hà-Van Tuyl曾讨论过，对于简单图G，如果图G的边理想的正则度对所有的s≥ 2 都有reg（I（G）s）=2s，那么Gc不含C4，即图G是gap-free 的.因此有如下猜想：如果图G是gap-free 的，那么对所有的正整数s≥2，都有图G的边理想的正则度都有reg（I（G）s）=2s.在研究这个猜想的过程中有如下思考：对于所有的gap-free图G，都有reg（I（G））≤ 3.

对于正则度小于等于3的图类，Nevo 等［2］首先证明了gap-free 且claw-free 图的边理想的正则度小于等于3.Banerjee［3］对此结果进行了推广，证明了gap-free且cricket-free图的边理想正则度reg（I（G））≤ 3，并且对于s≥ 2 都有reg（I（G）s）=2s，即I(G)s有线性的极小自由分解式.Erey［4］给出了新的图类gap-free 且diamond-free 图，证明了此类图的边理想的正则度reg（I（G））≤ 3，且对于s≥2，都有reg（I（G）s）=2s.刘阿明等［5］给出了chair-free 且gap-free 图类，证明了其边理想的正则度不超过3.在文献［6］中给出了kite-free 且gapfree图类，证明了其边理想的正则度不超过3.此外，也有诸多学者在gap-free的边理想及其幂的正则度上做了很多研究，具体内容可参考文献 ［7-8］.

本文研究的过程中只考虑不含有孤立点的连通图.因为对于gap-free图，如果图G不是连通图，则其2个不同连通分支不能同时含有边，即假设2个连通分支都含有边，那么这2条边就构成一个gap，因此gapfree图至多是一个连通分支与一些孤立点的并.容易证明，一个图加上一些孤立点之后，其边理想的正则度保持不变，因此只考虑不含有孤立点的连通gap-free图.

图G的子图M是指V（M）⊆V（G）且E（M）⊆E（G）.假设M是G的子图，若M的在G中相邻的顶点在M中也是相邻的，则称M是G的导出子图.

路径Pn是指顶点集为｛x1，x2，…，xn｝，边集E（Pn）满足xi-1xi∈E（Pn）当且仅当1≤i≤n-1的图，称n为路径Pn的长度.用d（x，y）表示点x与y之间最短路的长度.如果图G中的任意2个点都存在一条路径，则称图G是连通图.

图G的补图Gc是具有与G相同顶点集的图，uv∈Gc当且仅当uv∉G.圈Cn是指顶点集为｛x1，x2，…，xn｝和边集为｛x1x2，x2x3，…，xn-1xn，xnx1｝的图，称圈的补图为反圈.弦图是指图G不含有4以及以上的圈作为导出子图的图.如果｛u，v，a，b｝上的导出子图除uv和ab外没有其他边，则将2条不相交边uv和ab记为gap.

G中点v的邻点集记为NG（x），用stx表示NG（x）∪｛x｝.如果在G中删掉顶点v，记G-v是G的导出子图.完全图是指其任意2个顶点都是相邻的.

对于顶点集W⊆V（G），如果W中的任意2点都不相邻，则称W是图G的独立集.对于顶点集M⊆V（G），如果M中任意2点都相邻，则子集M是图G的团，用ω（G）表示图G的最大团的顶点个数.假设顶点集D是G的一个团，如果G中每个顶点都与D中的一个顶点相邻，则称D为图G的一个团覆盖.

根据图1 简单图的结构，容易得到以下结论；
如果G是claw-free 图，那么G是cricket-free 图；
如果G是claw-free 图，那么G是nest-free图；
如果G是C4-free图，那么G是nest-free图.注意到，nest-free且gap-free图不一定是cricket-free图，也不一定是diamond-free图，如图2所示.

图1 一些简单图

图2 nest-free且gap-free图

设M是有限生成的Zn-分次R-模，M的极小自由预解式是如下长度最小的正合列.

如果极小自由预解式具有以下形式，则称其为纯的自由预解式

Chung 等［9］证明了所有的gap-free 图都存在一个势为ω（G）的团覆盖，其相关引理将在文中将被多次使用.

引理1［9］如果G是gap-free且ω（G）≥ 3，那么G一定有一个势为ω（G）的团覆盖.

引理2［7］令I是环R的一个单项式理想，对任意I的生成元x，都有reg（I）≤max｛reg（I：x）+1，reg（I，x）｝，其中，（I：x）是冒号理想.

引理3［1］假设G是简单图，则边理想I（G）具有线性的极小自由预解式的充分必要条件是其补图Gc是弦图.

引理4［7］设x是图G的一个顶点，如果x的邻点集是｛y1，y2，…，yn｝，则有

因此reg（I（G））≤max｛reg｛G-stx｝+1，reg（G-x）｝，且reg（I（G））等于两者中的一个.

引理5［3］设G是一个gap-free 图且没有孤立点，如果x是图G最大度点，那么对于任意的点y，都有d（x，y）≤ 2.

假设G是nest-free且gap-free图，有下面3个主要结果.

假设中有一个点与y不相邻，不失一般性，假设y与中的v1不相邻，那么y与v2，v3，…，vn-2，vn-1和vn都相邻.因此，如图3 所示，图G在点集｛v1，vn-2，vn-1，vn，x，y｝上的导出子图构成一个nest 图，矛盾.

图3 反圈（n≥5）和边xy

综上所述，y与中所有的点都相邻.

命题2 设G是nest-free且gap-free图，如果x是G中最大度点，那么G-stx的补图是弦图且reg（Gstx）=2.

证明因为G是gap-free 图，所以（G-stx）c不含有C4作为导出子图，假设存在n≥5 使得Cn是（G-stx）c的导出子图.即是图G的一个反圈，如果x是y的一个邻点，那么根据命题1 可知y与中每一个点都相邻.因此，Cn中的点vi的度比x的度大，与假设x是最大度的点矛盾，此矛盾说明了（G-stx）c是弦图，再根据引理3，得reg（G-stx）=2.

命题3 如果G是nest-free且gap-free图，那么reg（I（G））≤ 3.

证明设x是图G的最大度点，因G是nest-free 且gap-free 图，所以G-x是nest-free 且gap-free 图，通过对G的顶点数的归纳，G-x的正则度不超过3，再由引理4 得，只需要证明（G-stx）c是弦图，根据命题2，结论成立.

容易看出，claw-free 图是nest-free 图；
C4-free 图是nest-free 图，cricket-free 图是nest-free 图，chair-free 图是nest-free图.因此，得到以下推论：

推论1［3］如果G是gap-free且cricket-free图，则reg（I（G））≤ 3.

推论2［10］如果G是gap-free且C4-free图，则reg（I（G））≤ 3.

推论3［2］如果G是gap-free且claw-free图，则reg（I（G））≤ 3.

推论4［5］如果G是gap-free且chair-free图，则reg（I（G））≤ 3.

对于kite-free且nest-free图，已知有如下结果：

命题4［6］设G是kite-free 且nest-free 图，假设其有反圈（n≥ 5）和边xy，如果点x与的所有点都不相邻，则y与中所有的点都相邻.

命题5［6］设G是kite-free 且gap-free 图，且x是G中最大度点，那么G-stx的补图是弦图且reg（Gstx）=2.

命题6［6］设图G是kite-free且gap-free，则reg（I（G））≤ 3.

基于上述关于gap-free的诸多结果，有如下猜想：

猜想1 如果图简单图G是gap-free的，那么reg（I（G））≤ 3.

猜想2 设G是gap-free图，如果reg（I（G））≤ 3，那么对所有的s≥ 2，都有reg（I（G）s）=2s.

假设图G是连通的简单图，定义n-gap 为顶点集｛v1，v2，…，vn，w1，w2｝和边集｛v1v2，v2v3，…，vn-1vn，w1w2｝的图（或记为Pn∪P2），则不含有n-gap作为导出子图称为n-gap-free图.

命题7 设图G是连通的n-gap-free 图，如果点x是图G中的最大度的点，那么对于任意的点y都有d（x，y）≤n.

证明反证法 假设存在点y满足d（x，y）=n+1，并设最大度点x的度为m，且x的邻点集记为｛y1，y2，…，ym｝.因为d（x，y）=n+1，所以存在最短路｛xx1，x1x2，x2x3，…，xn+1y｝.断定x只与x1相邻，而与｛x2，x3，…，xn+1，y｝都不相邻.事实上，如果x与｛x2，x3，…，xn+1，y｝中的某个点相邻，那么d（x，y）≤n，矛盾.｛x2x3，…，xn+1y｝是指Pn，即长度为n的路.对于所有的1 ≤i≤m由于｛xyi｝与｛x2x3，…，xn+1y｝构成n-gap.因此，x或yi必然与｛x2，x3，…，xn+1，y｝中的某个点相邻，但是x与｛x2，x3，…，xn+1，y｝都不相邻，所以只有yi与｛x2，x3，…，xn+1，y｝中的某个点相邻.假设yi与xj（j≥3）或者y相邻，那么d（x，y）≤n，矛盾.因此，yi与x2相邻.此时，对于所有的1≤i≤m，yi与x2相邻，那么d（x2）≥m+1，与d（x）=m矛盾.因此，假设不成立，命题得证.

引理6 设图G是3-gap-free图，且不含图4a和b作为导出子图，如果点x是图G中的最大度的点，那么图G-stx一定是连通3-gap-free图或者是一个连通分支与一些孤立点的并.

图4 gap-free图

证明由于G-stx是图G的导出子图，所以G-stx是3-gap-free 图，只需要证明G-stx是连通图或者是一个连通分支与一些孤立点的并即可.

反证法 假设G-stx是不连通的3-gap-free 图，且有2 个连通分支，分别为A和B.设x的邻点集为｛y1，y2，…，ym｝，不妨设这里的m≥ 3.这是因为，如果m=2，则图G是一条路或圈，其边理想的正则度为至多为3.

由于G是连通图，所以x与子图A中的每个点v之间存在一条路径，又因为x与子图A中点不相邻，所以存在A中的点v1与某个yi相邻，并设v1所在的边为｛v1v2｝.同样，在B中存在边｛w1w2｝与某个yj相邻.如果yi与v1和v2都相邻，则图G在｛x，yi，v1，v2｝的导出子图构成图4b，矛盾，所以yi只能与v1相邻.同样，yj只能与w1相邻.进一步，如果yi与点w1和w2不相邻，则图G在｛yi，v1，v2，w1，w2｝上的导出子图为3-gap，矛盾.因此，yi与点w1和w2中的某个点相邻，不妨设yi与点w1相邻.当yi与点w1相邻，则G在｛x，yi，v1，v2，w1｝上的导出子图构成图4a，矛盾.

综上所述，B中不存在边｛w1w2｝，因此G-stx一定是连通3-gap-free 图或者是一个连通分支与一些孤立点的并.

引理7 设图G是3-gap-free 图且不含图4a和b 作为导出子图，如果点x是图G中的最大度的点，那么图G-x一定是连通的3-gap-free图.

证明因为G-x是图G的导出子图，所以G-x是3-gap-free 图.只需证明3-gap-free 图是连通图或者是一个连通分支与一些孤立点的并.

反证法 假设G-x是不连通的3-gap-free 图，且有2 个连通分支，分别为A和B.设x的邻点集为｛y1，y2，…，ym｝，不妨设m≥ 3.事实上，如果m=2，则图G是一条路或圈，其边理想的正则度为至多为3.

假设点y1，y2在A中，y3在B中，如果y1，y2相邻，则图G在｛x，y1，y2，y3｝上的导出子图是图4b，矛盾；
如果y1，y2不相邻，由于B是连通图，必然存在w1使得｛w1，y3｝是一条边，所以图G在｛x，y1，y2，y3，w1｝上的导出子图是图4a，矛盾.因此，点y1，y2，…，ym必然都在A中.如果集合V（B）非空，假设B中存在点w1，由于A与B不连通，所以x与w1不存在路径，矛盾，因此集合V（B）是空集，即图G-x一定是连通的3-gap-free图.

命题8 设图G是3-gap-free图，如果图G不含图4a和b作为导出子图，那么reg（I（G））≤4.

证明对图G的顶点个数|G|做归纳，不妨设|G|≥4，点x是图G中的最大度点，由引理4 知：reg（I（G））≤ max｛reg｛G-stx｝+1，reg（G-x）｝.由于G-x是图G的导出子图.因此，G-x也是3-gap-free图.由归纳可知，reg（G-x）≤ 4.

对于导出子图G-stx，必然有reg｛G-stx｝ ≤ 2.事实上，只需要证明（G-stx）c是弦图即可.

反证法 假设（G-stx）c不是弦图，即（G-stx）c存在大于等于4 的圈Cm，不妨设V（Cm）=｛v1，v2，…，vm｝，E（Cm）=｛v1v2，v2v3，…，vn-1vm，v1vm｝.因为点x是图G中的最大度点，所以｛v1，v2，…，vm｝中的每个vj点到x的距离满足2 ≤d（x，vj）≤ 3.又因为E（Cm）=｛v1v2，v2v3，…，vn-1vm，v1vm｝是（G-stx）c的边，所以v1v3，v1v4是G-stx的边，且v3v4不是G-stx的边.如果d（x，v1）=d（x，v3）=2，则必然存在yi使得yi与v1，v3相邻.因此，图G在｛x，yi，v1，v3｝上的导出子图是图4b，矛盾.如果d（x，v1）=2，d（x，v3）=3，则必然有yi，使得yi与v1相邻，此时yi与v3不相邻.考虑点v4，如果yi与v4相邻，则图G在｛x，yi，v1，v4｝上的导出子图为图4b，矛盾；
如果yi与v4不相邻，则图G在｛x，yi，v1，v3，v4｝上的导出子图为图4a，矛盾.如果d（x，v1）=d（x，v3）=3，由于｛v1，v3，v4｝是P3，｛xyi｝是图G的边，因此v4必然与yi相邻，如果v2与yi相邻，则图G在｛x，yi，v2，v4｝上的导出子图为图4b，矛盾；
如果v2与yi不相邻，则图G在｛x，yi，v1，v2，v4｝上的导出子图为图4a，矛盾.因此，假设不成立，即（G-stx）c是弦图.

证毕.

考虑的3-gap-free 图都是连通图.如果图G不是连通图，则命题8 不成立，此反例可见文献［6］.假设图G的边理想I（G）=＜x1x2，x2x3，x1x3，x4x5，x4x6，x5x6，x7x8，x9x10，x11x12＞，用CoCoA 软件计算可得reg（I（G））=6 ＞4.

猜你喜欢 连通分支邻点子图 偏序集的序连通关系及其序连通分支高校应用数学学报A辑(2022年3期)2022-09-29围长为5的3-正则有向图的不交圈赤峰学院学报·自然科学版(2021年4期)2021-06-24关于图的距离无符号拉普拉斯谱半径的下界华中师范大学学报（自然科学版）(2021年3期)2021-06-10临界完全图Ramsey数同济大学学报（自然科学版）(2019年2期)2019-04-02基于频繁子图挖掘的数据服务Mashup推荐电子科技大学学报(2016年2期)2016-08-31特殊图的一般邻点可区别全染色山西大同大学学报(自然科学版)(2016年6期)2016-01-30一个图论问题的简单证明新课程(下)(2015年9期)2015-04-12交换环的素谱与极大谱的连通性纯粹数学与应用数学(2014年2期)2014-07-19不含2K1+K2和C4作为导出子图的图的色数华东师范大学学报（自然科学版）(2014年1期)2014-04-16笛卡尔积图Pm×Kn及Cm×Kn的邻点可区别E-全染色研究长江大学学报(自科版)(2014年7期)2014-03-20