{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圖.

1 一些符號和概念

圖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的極小自由預解式是如下長度最小的正合列.

如果極小自由預解式具有以下形式，則稱其為純的自由預解式

2 nest-free且gap-free圖邊理想的正則度

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.

3 n-gap-free圖及一些n-gap-free圖的邊理想的正則度

假設圖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.