一类特殊连通图的性质

韩 静,宋星星,李 玥

(1.山西大学商务学院 数学教学研究部，山西 太原 030031；2.山西大学商务学院 会计学院，山西 太原 030031)

0 引言

文中讨论的内容只涉及简单图，在简单图中一些基本定义详见[1,2].

设G是一个图，用V(G)表示其顶点集，E(G)表示其边集.顶点u∈V(G)在图G中的度是指定点u与图G中顶点集合相邻接的顶点的个集，记为dG(u)，不混淆时下角标G可省略，简记成d(u).我们记Δ(G)为图G中顶点度数的最大值，称为图G的最大度.令图G=(V(G)，E(G))，如果V′⊆V(G)并且E′⊆E(G),那么图H=(V′,E′)是图G的一个子图.对于顶点集V(G)的任意非空子集S，那么称以S为顶点集合，以两个端点都在集合S中的所有的边的集合构成的子图为G的由S导出的子图，极为G[S]，称集合NG(v)={uV(G)；uvE(G)}为点v在图G中的邻域.

我们称完全二部图K1,3为爪.令H是一个给定的图，如果G不包含H的导出子图，则图G被称为无H的.那么H被称为G的一个禁用子图.对于一个图类，如果对于每一个H∈，G都是无H的，那么图G被称为无的.

一般的，我们通常从图的参数角度去研究图的性质，例如：最小度，图的独立数，连通度等，详见[3-6].除此之外，从图的结构上去研究图的性质也是非常有意义的，通常我们考虑禁用某些特定的子图.最常见的禁用子图之一是K1,3，称不包含K1,3作为导出子图的那些图为无爪图，详见[7,8].

1 主要结论

我们主要研究了一类无{K1，3，P4}连通图的性质.这个问题的研究对我们研究不连通禁用子图对的刻画能带来一些帮助.

定理1令G是一类无{K1，3，P4}的连通图.则它的顶点集合可以划分成两个子集X和Y使得以下三个结论成立：

1)G[X]和G[Y]都是团；

2)|X|≥|Y|；

3)对于任意的两个顶点y1,y2∈Y，要么NG[X](y1)=NG[X](y2)，要么NG[X](y1)∪NG[X](y2)=|X|. 证明 如果Δ(G)<3，那么G是一条路或者是一个圈，因为G是无P4的，所以G是P1，P2，P3，C3或C4中的一个 (G∈{P1，P2，P3，C3，C4}).注意到K2也是一个团，因此我们很容易验证这些图都是满足定理中的三个结论.

如果Δ(G)≥3，那么G中包含K3做为一个导出子图，则我们一定能从G中找到一个极大团，设为C.令X=V(C)并且Y=V(G)X.则|X|≥3.注意到当|Y|<2时，定理成立.所以我们只需要考虑当|Y|≥2时的情形即可.

断言1对于任意的顶点y∈Y，NG[X](y)≠Ø都成立.

证明 如果存在一个顶点y∈Y使得，NG[X](y)=Ø，那么存在一个顶点y0∈Y使得d(y0,X)=2.令P=y0y1x1是y0与X之间的最短路.则x1∈X并且y1∈Y.注意到G[X]是G中的一个极大团.则存在一个顶点x0∈X使得x0y1∉E(G).因此G[{x0，x1，y1，y0}]≌P4，矛盾.

接下来，我们首先断言G[Y]是一个团.否则存在两个顶点y1,y2∈Y使得y1y2∉E(G).因此我们分以下两种情形：

情形1要么NG[X](y1)NG[X](y2)=Ø，要么NG[X](y1)NG[X](y2)=Ø.

不失一般性，我们假设NG[X](y1)NG[X](y2)=Ø.这意味着NG[X](y1)⊆NG[X](y2).因此存在一个顶点x0∈X使得x0y1，x0y2∈E(G).注意到G[X]是G中的一个极大团，则|NG[X](y1)|≤|NG[X](y2)|<|X|.因此存在一个顶点x1∈X使得x1y1，x1y2∉E(G).则G[{x0，x1，y1，y2}]≅K1,3,矛盾.

情形2NG[X](y1)NG[X](y2)≠Ø并且NG[X](y1)NG[X](y2)≠Ø.

这意味着有两个顶点x1，x2∈X使得x1y1，x2y2∈E(G)并且x1y2，x2y1∉E(G).因此，G[{y1，x1，x2，y2}]≅P4，矛盾.

接下来，因为G[X]是G中的一个极大团，所以|X|≥|Y|.最后，我们来证明结论3).

令y1和y2是Y中的两个顶点.假设NG[X](y1)≠NG[X](y2)并且NG[X](y1)∪NG[X](y2)≠|X|.则存在两个顶点x0，x1∈X使得x0y1，x0y2∉E(G)并且要么x1∈NG[X](y1)NG[X](y2)要么x1∈NG[X](y2)NG[X](y1).不失一般性，我们假设x1∈NG[X](y1)NG[X](y2).这意味着x1y1∈E(G)并x1y2∉E(G).这说明G[{x0，x1，y1，y2}]≅P4，矛盾.

因此，定理1成立.证毕.