最大分数f-因子的注记

高 炜

(云南师范大学 信息学院，云南 昆明 650500)

1 预备知识

若f≡g，则分数(g,f)-因子称为分数f-因子．若g(x)=a，f(x)=b对任意顶点x都成立，则分数(g,f)-因子称为分数[a,b]-因子．特别地，若对任意顶点x有g(x)=f(x)=k，则分数(g,f)-因子称为分数k-因子．

假设图G存在多个分数f-因子，把拥有最多边数的分数f-因子称为图G的最大分数f-因子．为了刻画最大分数f-因子的特征，首先在分数f-因子框架下给出在符号交错路，调整操作以及增广路的概念．

约定本文中给出的路径允许每条边最多出现两次．设Gh1和Gh2是图G分别关于示性函数h1和h2的分数f-因子．记

图G关于示性函数h的增广路W是一条长度为偶数的闭路径，它的边在大于0和小于1之间交替，且至少有一条边在h下的值为0．若将增广路定义为边的序列W=(e0,e1,…,e2m-1,e0)，则对于0≤r≤m-1有h(e2r)<1和h(e2r+1)>0成立，且对某些i有h(e2i)=0．

2 主要结论及证明

下述定理1说明了图G的任何两个分数f-因子可以通过有限次调整操作进行相互转换．

定理1设Gh1和Gh2是图G分别关于示性函数h1和h2的分数f-因子．则Gh2可以由Gh1通过有限次重复调整操作得到．

证明假设f≠g，定义边集合

Eh1≠h2={e∈E(G):h1(e)≠h2(e)}.

下面说明H中存在关于示性函数h1和h2的符号交错路．假设符号交错圈不存在，则在H中取长度最长的符号交错路P=x1x2…xm．不妨设Δh1,h2(x1x2)>0，下面分两种情况讨论．

1)若m是奇数，则Δh1,h2(xm-1xm)<0． 由于δ(H)≥2， 必然存在i,j∈{1,2,…,m}使得Δh1,h2(x1xi)<0和Δh1,h2(xmxj)>0成立． 从而C1=(x1,…,xi,x1)和C2=(xj,…,xm,xj)均为奇圈． 若i>j， 则C=(x1,…,xj,xm,…,xi,x1)是H的符号交错圈； 若i≤j，则C=(x1,…,xi,…,xj,…,xm,xj,…,xi,x1)是H的符号交错圈．

2)若m是偶数，则Δh1,h2(xm-1xm)>0． 由于δ(H)≥2， 必然存在i,j∈{1,2,…,m}使得Δh1,h2(x1xi)<0和Δh1,h2(xmxj)<0成立． 从而C1=(x1,…,xi,x1)和C2=(xj,…,xm,xj)均为奇圈． 若i>j， 则C=(x1,…,xj,xm,…,xi,x1)是H的符号交错圈； 若i≤j， 则C=(x1,…,xi,…,xj,…,xm,xj,…,xi,x1)是H的符号交错圈．

下述定理2刻画了最大分数f-因子的特性．

定理2设Gh是图G分别关于示性函数h的分数f-因子．则Gh是最大分数f-因子当且仅当G不存在关于h的增广路．

证明设Gh是最大分数f-因子且G存在增广路C=(e1,e2,…,em)． 设E′(C)={e∈E′(C):0

不失一般性，可以设h(e1)=0． 设：h′(ei)=ε若i是奇数；h′(ei)=-ε若i是偶数；h′(e)=0若e∈E(G)-E(C)． 则Gh+h′是G的关于示性函数h+h′的分数f-因子，而它的边数为大于Gh的边数，这与Gh是最大分数f-因子的假设矛盾．

反之，设G中没有关于h的增广路，证明Gh是G的最大分数f-因子．否则，设Gh′是G的最大分数f-因子，对应示性函数h′，且|Eh′|>|Eh|． 进而至少存在一条边e1∈E(G)使得h′(e1)>0和h(e1)=0成立． 根据定理1，Gh′可以由Gh通过一些列调整操作得到， 且设h=h0,h1,…,hs-1,hs=h′是调整超过过程中对应的示性函数序列，r是满足hr-1(e1)=0和hr(e1)>0的最小下标． 进而在Ghr-1中存在符号交错圈C=(e1,e2,…,em)包含e1．根据符号交错路的定义可知：对任意满足h(e)h′(e)的e∈E(C)， 有hr-1(e)>hr(e)． 进而有： 对所有满足h(e)h′(e)的e∈E(G)， 对任意i=0,1,…,s-1有hi(e)≥hi+1(e)．进一步，对奇数j，有

h(ej)≤hr-1(ej)

对偶数j，有

h(ej)≥hr-1(ej)>hr(ej)≥h′(ej)≥0.

根据e1的选择可知C是G中关于示性函数h的增广路，与假设矛盾．

3 小结和讨论

本文指出图G的两个不同两个分数f-因子可以通过有限次调整操作进行相互转换，并且从增广路的角度给出Gh是最大分数f-因子的充分必要条件．然而本文中给出的定理1和定理2无法直接推广到分数(g,f)-因子或者分数[a,b]-因子，其根本原因在于不同分数(g,f)-因子或分数[a,b]-因子在具体某个顶点上的值不固定，导致定理1证明过程中的δ(H)≥2不一定成立．而定理2的证明是基于定理1的，因此定理2也无法直接推广．关于最大分数(g,f)-因子或最大分数[a,b]-因子的刻画，还需要进一步研究．