限制度的IC平面图中轻弦4-圈的权和

田 京 京

(陕西理工大学 数学与计算机科学学院, 陕西 汉中 723000)

1 引言与预备知识

图论因其表述能力强和算法高效在大数据分析中应用广泛. 图的结构问题是图论研究的核心问题之一, 是图论理论研究及图染色和标号模型[1-3]的基础. Ringel[4]在研究平面图的点-面染色时提出了1-平面图的概念, 之后, Albertson[5]提出了IC-平面图的概念. 目前平面图中轻子图的研究已取得一些成果[6-8]: Kotzig[6]证明了任意3-连通的平面图包含一条边, 且与这条边所关联的两顶点的度之和至多为13; Fabrici等[9]证明了每个3-连通的1-平面图含有一条轻边且轻边高度的上界为20, 并证明了最小度至少为6的1-平面图包含一个3-圈uvw, 且max{d(u),d(v),d(w)}≤10; Hudk等[10]证明了最小度至少为6的1-平面图包含一个4-圈, 且4-圈上点的度至多为47; Zhang等[11]证明了最小度至少为6的1-平面图包含一个4-圈, 且4-圈上点的度至多为19, 以及在最小度为7的1-平面图中含有轻K4且轻K4高度的上界是11； Tian等[12]证明了每个最小度至少为5的NIC-平面图含有一个3-圈uvw, 且max{d(u),d(v),d(w)}≤26; 田京京等[13]证明了每个最小度至少为5且最小边度至少为11的IC-平面图G轻3-圈高度的上界为17; Niu等[14]证明了最小度至少为3的1-平面图中存在轻边. 本文利用权转移的方法讨论最小度为5且最小边度为11的IC-平面图中含有轻弦4-圈且权和的上界小于等于37.

定义1[5]图G称为1-平面图, 当且仅当图G可画在一个平面上, 且每条边至多被交叉一次. 若G上存在交叉点, 则必为G的某两条边交叉产生, 于是G中每个交叉点c都可与G中的4个顶点(即两条交叉边上的4个顶点)所构成的点集建立对应关系, 该对应关系记为S. 显然在一个好的1-平面图画法(即交叉点最少的画法)中, 对于任意两个交叉点c1,c2, 存在|S(c1)∩S(c2)|≤2. 若1-平面图的两个子类满足|S(c1)∩S(c2)|=0, 则称该1-平面图为IC-平面图.

定义3[11]如果将图G中的所有交叉点均视为4-度点, 则可得一个交叉数为0的图G×, 称为G的关联图. 设v是图G×中的一个点, 如果v∈V(G×)V(G), 则称v是G×的一个假点或称v是G的一个交叉点, 否则称v为G×的一个真点. 设uv是图G×中的一条边, 如果uv∈E(G)E(G×), 则称uv是G×的一条假边或称其为G的一条交叉边, 否则称uv为G×的一条真边. 设f是图G×的一个面, 如果f关联至少一个假点, 则称f为G×的一个假面, 否则称f为G×的一个真面. 由关联图G×的定义知, 对于G中的每个点v, 总有dG(v)=dG×(v). 图G中任意一条边uv所关联的点u,v度之和d(u)+d(v)称为边uv的度.

本文讨论的图类范围仅限于简单的有限无向图, 分别用V(G),E(G),F(G),Δ(G),δ(G)表示G中的点集合、 边集合、 面集合、 最大度和最小度. 用k-,k+-和k--点或面分别表示一个点或面的度为k(至少为k和至多为k). 对于G中的一个点v, 用fk(v)表示v在G×中关联的k-面个数, 用nc(v)表示v在G×中相邻的假点个数. 设v是G×中的k-点,v1,v2,…,vk是v在G×中按顺时针排列的所有邻点. 在G×中与边vvi和vvi+1关联的面记为fi(1≤i≤k), 并记vk+1∶=v1. 其余定义若无特殊说明均参考文献[15].

2 主要结果

定理1每个最小度至少为5且最小边度至少为11的IC-平面图含有一个弦4-圈v1v2v3v4v1, 且d(v1)+d(v2)+d(v3)+d(v4)≤37.

证明： 反证法. 假设结论不真, 则存在一个反例G, 其所包含的任意一个弦4-圈v1v2v3v4v1都满足d(v1)+d(v2)+d(v3)+d(v4)≥38. 设G×是G的关联图, 给G×中的每个点v赋初始权值为c(v)=d(v)-6, 并给G×中的每个面f赋初始权值为c(f)=2d(f)-6, 根据平面图G×上的Euler公式, 有

按如下规则对V(G×)∪F(G×)上的所有元素重新分配权值.

1) 设f=xyz是G×中的一个3-面,d(x)=m.

① 若x是7-点,z是4-点, 则x向z转移3/10； 若x是8-点,z是4-点, 则x向z转移1; 若x是9-点,z是4-点, 则x向z转移8/9; 若x是10+-点,z是4-点, 则x向z转移1.

② 若x是7-点,z是5-点, 则x向z转移1/10； 若x是8-点,z是5-点, 则x向z转移1/10; 若x是9-点,z是5-点, 则x向z转移1/9; 若x是10+-点,z是5-点, 则x向y转移(m-8)/m.

③ 若f是真3-面且yz关联一个假3-面f′=yzs, 其中7≤d(x)≤9, 则x通过yz向s转移1/2; 若f是真3-面且yz关联一个假3-面f′=yzs, 其中x是一个10+-点, 则x通过yz向s转移1/2.

设f是G×中的一个4+-面.

①f向其关联的4-点转移1.

②f向其关联的5-点转移1/2.

③ 若f的某条边xy关联一个3-面f′=xyz且z是4-点, 则f通过xy向z转移1/2.

设c′(x)为元素x∈V(G×)∪F(G×)在应用上述权转移规则后得到的新权值, 下面证明对每个x∈V(G×)∪F(G×)都有c′(x)≥0. 因此,

矛盾.

首先, 验证对任意的f∈F(G×), 有c′(f)≥0.

若d(f)=3, 则由规则1),2)知c′(f)=c(f)=0. 若d(f)=4, 则由G的最小边度至少为11知, 面f最多关联2个5-点. 若面f关联1个4-点, 则由IC-平面图的定义知, 规则2)中③不可能再应用于面f, 因此, 由规则2)中①,②可知

另一方面, 若面f不关联4-点, 则由IC-平面图的定义知, 规则2)中③最多应用于面f两次, 因此, 由规则2)中①,③可知

若d(f)=5, 则考虑下列两种情形.

(i) 若面f不关联4-点, 则由G的最小边度至少为11知, 面f最多关联2个5-点. 由IC-平面图的定义知, 规则2)中③最多应用于面f两次. 因此, 由规则2)中②,③可知

(ii) 若面f关联1个4-点, 则由G的最小边度至少为11知, 面f最多关联2个5-点. 由IC-平面图的定义知, 规则2)中③最多应用于面f一次. 因此, 由规则2)中①,②,③可知

其次, 验证对任意的v∈V(G×), 有c′(v)≥0.

根据规则1),2)知, 图G×中的6-点不参与权转移, 因此d(v)=6, 从而c′(v)=c(v)=d(v)-6≥0. 下面考虑6种情形.

情形1)d(v)=4.

① 若v至少关联2个4+-面, 则由规则2)中①得c′(v)≥4-6+1×2=0.

② 若v仅关联1个4+-面, 不妨设其为f1, 则f2,f3,f4均为3-面. 假设v1,v2,v3,v4中不存在1个10+-点, 则v1,v2,v3,v4一定是9--点, 于是这4个点的度之和为36, 与图G上任意一个弦4-圈上点的度之和均大于等于38矛盾, 所以v1,v2,v3,v4中存在一个10+-点. 由规则1)中①知v4向v转1, 由规则2)中①知f1向v转1, 故c′(v)≥d(v)-6+1×1+1×1=0.

③ 若v仅关联3-面, 即f1,f2,f3,f4均为3-面, 则由G是一个反例知,G中弦4-圈上4个点度之和大于等于38, 因此, 可分下列几种情形讨论.

(i) 若观察v1,v2,v3,v4中任意三点, 可发现这三点至少有2个6点或2个7点, 且三点的度之和大于等于17, 小于等于21, 于是v1,v2,v3,v4中剩下的那个点是17+-点, 不妨设为v4. 根据规则1)中①可知v4向v转1. 此时与v2v3关联的另一个面或者是4+-面, 或者是真3-面f′=v2v3u, 其中u为17+-点. 同时,v3v4关联的另一个面或者是4+-面, 或者是真3-面f′=v3v4w, 其中w为17+-点. 因此, 根据规则1)中①,③和2)中③可知

(ii) 若v1,v2,v3,v4中任意两点度之和小于等于18, 剩余两点为10+-点, 则由规则1)中①得

c′(v)≥d(v)-6+1×2=0.

(iii) 若v1,v2,v3,v4中有3个8-点, 则由规则1)中①得

(iv) 若v1,v2,v3,v4中有2个8-点、 1个7-点、 1个15+-点, 则由规则1)中①得

(v) 若v1,v2,v3,v4中有2个8-点、 1个9-点、 1个13+-点, 则由规则1)中①得

情形2)d(v)=5.

① 若v至少关联2个4+-面, 则由规则2)中②得

② 若v仅关联1个4+-面, 不妨设其为f1, 则f2,f3,f4,f5均为3-面. 由G的IC-平面性可知,v1,v2,v3,v4,v5中仅有1个4-点, 设d(v3)=4. 由最小边度为11知,v1,v2,v4,v5均是6+-点. 由于G是一个反例, 因此图G上任意一个弦4-圈上点的度之和都大于等于38. 因此分为如下几种情形讨论.

(i) 设d(v2)=6,d(v5)=6,d(v1)=6,d(v4)≥21. 由规则1)中②知v5向v转移(m-8)/m=13/21, 由规则2)中②知f1向v转移1/2, 故有

(ii) 设d(v2)=9,d(v1)=9,d(v5)≥16,d(v4)≥8. 由规则1)中②知v5向v转移(m-8)/m=1/2, 由规则2)中②知f1向v转移1/2, 故有

(iii) 设d(v1)=d(v2)=7,d(v4)=d(v5)=13+. 由规则1)中②知v5向v转移(m-8)/m=5/13, 由规则2)中②知f1向v转移1/2, 故有

(iv) 设d(v1)=d(v2)=8,d(v4)=13+,d(v5)=12. 由规则1)中②知v5向v转移(m-8)/m=1/3, 由规则2)中②知f1向v转移1/2, 故有

(v) 设d(v1)=d(v2)=9,d(v4)=d(v5)=12+. 由规则1)中②知v5向v转移(m-8)/m=1/3, 由规则2)中②知f1向v转移1/2, 故有

(vi) 设d(v1)=d(v2)=10,d(v4)=11,d(v5)=12+. 由规则1)中②知v5向v转移(m-8)/m=3/11, 由规则2)中②知f1向v转移1/2, 故有

(vii) 设d(v1)=d(v2)=11,d(v4)=11,d(v5)=11+. 由规则1)中②知v转移(m-8)/m=3/11, 由规则2)中②知f1向v转移1/2, 故有

③ 若v关联的全是3-面, 则由G的IC-平面性可知v1,v2,v3,v4,v5中仅有1个4-点. 设d(v3)=4, 由最小边度为11知,v1,v2,v4,v5均是6+-点. 由于G是一个反例, 因此图G上任意一个弦4-圈上点的度之和都大于等于38. 因此可分如下几种情形讨论.

(i) 若v1,v2,v3,v5中有2个16+-点, 则根据规则1)中②知v5向v分别转移(m-8)/m=1/2, 故

(ii) 若d(v1)=d(v3)=9,d(v2)=15+,d(v5)=15+, 则根据规则1)中②知,v2,v5向v转移(m-8)/m=7/15,v1,v3向v转移1/9, 故

(iii) 若d(v1)=d(v3)=10,d(v2)=13+,d(v5)=13+, 则根据规则1)中②知,v5向v转移(m-8)/m=5/13,v5向v转移(m-8)/m=1/5, 故

(iv) 若v1,v2,v4,v5均是11+-点, 则根据规则1)中②知,v1,v2,v4,v5分别向v转移(m-8)/m=3/11, 故

情形3)d(v)=7.

情形4)d(v)=8.

情形5)d(v)=9.

情形6)d(v)≥10.

不妨设fi1,fi1+1,…,fi1+t1-1,fi2,fi2+1,…,fi2+t2-1,…,fik,fik+1,…,fik+tk-1为与v关联的所有3-面(其在v的周围按顺时针排列), 其中当k≥2时, 对所有的1≤s≤k-1,fis+ts-1与fis+1不相邻, 且fik+tk-1与fi1也不相邻, 此时d=10. 注意到上述下标中的加法运算是在模d意义下进行的, 且当k=1时,fi1+t1-1与fi1可能相邻(此时与v关联的面均为3-面). 显然, 有如下不等式：