给定零维数的单圈图研究

何博瑞，房明磊

(安徽理工大学 数学与大数据学院，安徽 淮南 232001)

零度问题的研究是图论中一个热门问题.20世纪50年代，Collatz和Sinogowitz提出关于刻画所有奇异图的问题.过去二十年，关于图的零度问题吸引了众多的图论学家和化学家的注意力.在文献[1-11]中，作者对单圈图的零度关系进行了广泛研究.谭学忠和柳柏濂[1]刻画了η(G)=n-4所有图.郭继明[2]刻画了η(G)=n-5所有图.本文考虑η(G)=n-6和η(G)=n-7的所有n阶单圈图，并刻画了所有的满足条件的图.

1 基本理论

2 主要结果

定理1设G是n(n≥6)阶单圈图，则η(G)=n-6当且仅当G属于图类Gi(i=1,2,…,31)(见图4).

证明假设G的圈长为l，根据引理1、引理2和引理3，可以得到以下情况.

情况1η(G)=n-6=n-2v(G)-1=η(G)，显然2v(G)=5，因为匹配数均为正整数，所以不成立.

a.考虑在圈C4={v1,v2,v3,v4}顶点v1连接一条匹配数为1的树，显然匹配数为1的树仅有一类情况，如图1所示.考虑在圈上其中一个顶点处外接一个悬挂点，有三种连接方式，如v1,v2,v3或v1,v3,v4，均成立，此时图G仅可能是图4中的G1,G2,G3,G4.

图1 匹配数为1的树

b.当在圈C4的顶点处外接两个悬挂点和一个匹配数为1的树，此时有三种方式，分别是v1v2,v1v3,v2v3或v1v3,v1v4,v2v3，但其中两个悬挂点连接方式为v1v2或v1v4时，图G的匹配数为4，所以不成立，其余情况成立，此时，图G只能是图4中的G5,G6.

a.G=C6显然成立，因此，图G只能是图4中的G7.

b.考虑在圈长为6的图外加一个悬挂点成立，因此，图G只能是图4中的G8.

c.考虑在圈长为6的图外加两个悬挂点，当连接方式间隔点为偶数时导致v(G)=4矛盾，间隔奇数点时成立，因此，图G只能是图4中的G9.

d.考虑在圈长为6的图外加三个悬挂点，仅有连接在间隔奇数的顶点上成立，否则图G的匹配数是4，不成立，因此，图G只能是图4中的G10.

a.匹配数为2的树仅有三种情况，如图2所示的K1,K2和K3.

图2 圈连接匹配数为2的树

连接方式为K1时，在圈C4上连接一个悬挂点有三种方式，连接的顶点分别是v1,v2,v3或v1,v3,v4.因为树的匹配数为2已固定，此时相当于在圈长为4的顶点v1上固定一个悬挂点，接着在顶点v1,v2,v3或v1,v3,v4上再加一个悬挂点.加了两个悬挂点，图的匹配数依旧是2，情况成立.当悬挂点连接个数超过两个时，相当于是在圈C4上连接三个悬挂点，此时圈C4连接三个悬挂点使得它的匹配数为3，因此，图G的匹配数超过了3，所以悬挂点超过两个，均不成立，此时图G只能为图4中的G11,G12,G13,G14.

连接方式为K2时，在圈上连接一个悬挂点有三种，分别连接v1,v2,v3或v1,v3,v4.在v1处连接悬挂点时由于不满足引理3的条件E1∩M=φ，不成立.其余情况同K1连接情况一样，因此，图G只能为图4中的G15,G16,G17.

连接方式为K3时，不满足引理3的条件E1∩M=φ，不成立.

b.当连接两个匹配数为1的树时，根据图1所示，连接在圈长为4的图上有三种连接方式.如图3所示K4,K5和K6.

图3 圈长为4的图连接两个匹配数为1的树

连接方式为K4时，在圈上连接一个悬挂点有三种情况，分别连接顶点v1,v2,v3或v1,v3,v4，同K1连接情况一样，因此，图G只能为图4中的G18,G19,G20,G21.

连接方式为K5时，连接一个悬挂点有两种情况，分别是连接两个顶点v1v2,v2v3，但连接在树与圈的顶点v1v2与条件E1∩M=φ矛盾，不成立，此时图G只能为图4中的G22,G23.

连接方式为K6时，连接一个悬挂点有两种情况，但连接在树与圈的顶点上v1或v3时与条件E1∩M=φ矛盾，不成立，此时图G只能为图4中的G24,G25.

图4 零维数为n-6的单圈图

图4(续) 零维数为n-6的单圈图

(2)当l=6时，由于条件有l=0(mod4)，不满足，所以没有圈长为6的图.

a.G=C8显然成立，因此，图G只能为图4中的G26.

b.当考虑在圈外连接一个悬挂点时成立，因此，图G只能为图4中的G27.

c.考虑在圈长为8的图外连接两个悬挂点，当间隔点为偶数时导致v(G)≠4，矛盾.间隔奇数点时成立，有两种连接方式，因此，图G只能为图4中的G28,G29.

d.考虑在圈长为8的图外连接三个悬挂点，当间隔点为偶数时导致v(G)≠4，矛盾.间隔奇数点时成立，仅有一种连接方式，因此，图G只能为图4中的G30.

e.考虑在圈长为8的图外连接四个悬挂点，当间隔点为偶数时导致v(G)≠4，矛盾.间隔奇数点时成立，仅有一种连接方式，因此，图G只能为图4中的G31.证毕.

定理2设G是n(n≥7)阶的单圈图，则η(G)=n-7，当且仅当G属于图类Ui(1,2,…,7)(见图5).

图5 零维数为n-7的单圈图

证明假设图G的圈长为l，通过引理1、引理2和引理3有以下情况：

(1)如果l=7，那么，有v(G-Cl)=0，v(G)=3，若在圈外增加悬挂点则会导致图G的匹配数增加，因此，仅有G=C7，此时图G只能是图5中的U1.

(2)如果l=5，那么，有v(G-Cl)=1，因此，在圈长为5的图外面连接一个匹配数为1的树(如图1所示).若在圈外再连接悬挂点，那么，导致v(G)≠3，只有一种连接方式，因此，仅有G=C7，此时图G只能是图5中的U4.

(3)如果l=3，那么，有v(G-Cl)=2.说明在圈外将会连接一个匹配数为2的树(如图2所示)，或者连接两个匹配数为1的树(如图3所示).同理，若在圈外再连接悬挂点，则会导致v(G)≠3，因此，仅有G=C7，此时图G只能是图5中的U2,U3,U5,U6,U7.

情况2有η(G)=n-7=n-2v(G)=η(G)，那么，2v(G)=7，由于匹配数为整数，所以这类情况不存在.

情况3有η(G)=n-7=n-2v(G)+2=η(G)，那么，2v(G)=9，由于匹配数为整数，所以这类情况也不存在.证毕.