《Mathematics》:The Independent Bondage Number of Planar Graphs Without Short Cycles
编辑推荐:
图G的独立支配集I是一个独立集,使得V(G)-I中的每个顶点在I中至少有一个邻居。G的独立支配数是G的最小独立支配集的基数。图G的独立束缚数,记为bi(G),是使G的独立支配数增加所需删除的最小边集的基数。2025年,Gamlath等人证
图G的独立支配集I是一个独立集,使得V(G)-I中的每个顶点在I中至少有一个邻居。G的独立支配数是G的最小独立支配集的基数。图G的独立束缚数,记为bi(G),是使G的独立支配数增加所需删除的最小边集的基数。2025年,Gamlath等人证明,对于最小度δ(G)≥2的平面图G,若G不含长度为3和4的圈,则bi(G)≤5;若G不含长度为3、4、5和6的圈,则bi(G)≤4。这促使研究人员研究最小度δ(G)≥2且不含长度为4和5的圈,或长度为4、5、6和7的圈的平面图的独立束缚数。在本文中,研究人员证明了以下关于最小度δ(G)≥2的平面图G的界:若G不含长度为4和5的圈,则bi(G)≤5;若G不含长度为4、5、6和7的圈,则bi(G)≤4。
**论文解读:无短圈平面图的独立束缚数上界**
**研究背景与问题**
在图论中,支配集与独立支配集是经典概念。图G的独立支配集是指一个独立集,使得图中所有不在该集中的顶点至少有一个邻居在集中。独立支配数(independent domination number,记为γ
i(G))是此类集合的最小基数。独立束缚数(independent bondage number,记为b
i(G))则定义为使γ
i(G)增加所需删除的最小边集的大小。该参数由Zhang、Liu和Sun于2003年引入,其判定问题已被证明是NP困难的(即使对于二分图)。因此,寻找特定图类的上界成为重要研究方向。
对于平面图,Priddy等人证明了连通平面图G的独立束缚数满足b
i(G) ≤ Δ(G) + 1(Δ(G)为最大度),但是否存在普适常数上界?2022年,Pham和Wei解决了该问题,证明对于最小度δ(G) ≥ 2的平面图G,b
i(G) ≤ 8。为了获得更紧的界,研究者常对平面图施加结构限制,如禁止特定长度的圈。2025年,Gamlath等人证明了:若平面图G满足δ(G) ≥ 2且不含3-圈和4-圈,则b
i(G) ≤ 5;若同时不含3、4、5、6-圈,则b
i(G) ≤ 4。Kerdjoudj和Chellali则研究了禁止4-圈和5-圈的情形,但要求最小度δ(G) ≥ 3,得到了b
i(G) ≤ 5。
当前研究的问题是:能否在较弱的最小度条件(δ(G) ≥ 2)下,针对禁止不同长度圈组合的平面图,建立更紧的独立束缚数上界?特别是,当图不含4-圈和5-圈,或不含4、5、6、7-圈时,能否得到与Gamlath等人结果类似的上界?这些禁止圈条件与围长(girth)条件互为补充,因为禁止4-圈和5-圈仍允许3-圈,而围长≥7则禁止所有3-圈。本研究旨在填补这些空白,为平面图独立束缚数提供新的上界。
**研究内容与结论**
本文主要得到两个定理。定理1:对于最小度δ(G) ≥ 2且不含4-圈和5-圈的平面图G,有b
i(G) ≤ 5。这改进了Kerdjoudj和Chellali的结果(后者要求δ(G) ≥ 3)。定理2:对于最小度δ(G) ≥ 2且不含4、5、6、7-圈的平面图G,有b
i(G) ≤ 4。该结果与Gamlath等人的围长≥7结果互补,因为后者排除3-圈而允许7-圈,本文则允许3-圈但排除7-圈。两个定理均通过反证法,结合结构分析和放电法完成证明,并发表在《Mathematics》期刊。
**主要关键技术方法**
本文采用的主要技术方法包括:(1)反证法:假设存在最小反例图G,满足条件但独立束缚数大于目标上界;(2)结构引理分析:利用最小度条件、独立束缚数的性质(如定理3:若图H有边,则b
i(H) ≤ Δ(H))推导局部度限制,如2-顶点的邻居必须为高次顶点,以及3-圈上顶点的度约束;(3)放电法:对每个顶点和面赋予初始电荷(顶点4-d(v),面2d(f)-6),通过设计局部放电规则重新分配电荷,最终证明所有顶点和面的最终电荷非负,与总电荷为负的欧拉公式矛盾,从而否定反例存在。放电规则根据顶点度数(如2-顶点、3-顶点、5-顶点等)和面类型(坏3-面、半坏3-面、好3-面等)定制,以处理不同结构。
**研究结果**
**第1节 引言**
介绍了独立支配数、独立束缚数的定义及研究背景,指出独立束缚数的判定问题NP-hard,并回顾了平面图独立束缚数的已知上界,包括Pham和Wei的常数上界以及Gamlath等人、Kerdjoudj和Chellali的禁止圈结果。通过表1和图1对比了不同禁止圈条件与围长条件的异同,说明本文考虑的条件允许3-圈,与围长条件互补。
**第2节 公共结构结果**
建立了两个定理证明中共同的结构引理。引理1说明反例的每个连通分支也是反例。引理2利用定理3(b
i(H) ≤ Δ(H))推导出:若δ(G) ≥ 2且b
i(G) > 5(或b
i(G) > 4),则2-顶点的邻居必须是≥9-顶点(或≥10-顶点);3-圈上顶点的度也受限制。引理3给出顶点v的3-面关联次数t
3(v)与好2-邻居数g(v)之间的关系。引理4-6处理坏2-顶点在圈和面边界上的出现次数,特别地,引理6给出?-面中坏2-顶点出现次数的上界。
**第3节 定理1反例的结构性质**
假设定理1反例存在,则G为连通平面图且δ(G) ≥ 2,无4-圈和5-圈,但b
i(G) > 5。引理7-9进一步限制5-顶点的结构:引理7表明若5-顶点v有多个好2-邻居,则可通过构造独立集得到矛盾;引理8证明若5-顶点v有4个好2-邻居,则其剩余邻居为≥9-顶点;引理9证明若5-顶点v关联一个半坏3-面,则其好2-邻居数至多为2。这些结构限制用于后续放电分析。
**第4节 定理1的放电论证**
对反例G应用放电法。初始电荷:顶点ch(v)=4-d(v),面ch(f)=2d(f)-6,总电荷为-8。放电规则(R1-R4)针对不同顶点和面进行电荷转移,例如(R1.1)好2-顶点从每个邻居接收1电荷,(R1.2)坏2-顶点从每个关联面接收1电荷,(R2)4-顶点向每个关联3-面送出1电荷,(R3)5-顶点根据3-面类型送出不同电荷等。通过分情况验证所有顶点和面的最终电荷非负,与总电荷为负矛盾,从而证明反例不存在,定理1得证。
**第5节 定理2反例的结构性质**
假设定理2反例存在,则G为连通平面图且δ(G) ≥ 2,无4、5、6、7-圈,但b
i(G) > 4。引理10指出3-面不能与≥8-面相邻。引理11给出顶点v的3-面关联次数与度数的关系。引理12限制2-顶点类型:若顶点v的所有不在3-面上的邻居都是好2-顶点,则这些好2-顶点不能是(6, ≥8)-顶点(即关联一个6-面和一个≥8-面)。
**第6节 定理2的放电论证**
类似地,对反例G应用放电法,初始电荷相同。放电规则(R1-R4)更精细:例如(R1.2)(3,3)-2-顶点从相邻顶点接收1电荷;(R1.3)(3,6)-2-顶点从相邻顶点接收1/2电荷;(R1.4)(3,≥8)-2-顶点从相邻顶点接收2/3电荷;(R4)≥8-面向每个非坏2-顶点的顶点关联出现送出1/3电荷。通过分情况(包括2-顶点、3-顶点、4-顶点、5-顶点、≥6-顶点、3-面、≥8-面)验证最终电荷非负,推出矛盾,定理2得证。
**第7节 结论与未来工作**
总结定理1改进了Kerdjoudj和Chellali的结果(将最小度条件从δ(G) ≥ 3降低到δ(G) ≥ 2),定理2与Gamlath等人的围长结果互补。指出两个定理的界是否紧尚待研究,即是否存在平面图达到b
i(G)=5(定理1)或b
i(G)=4(定理2)?此外,问题1提出:是否对于所有最小度δ(G) ≥ 2且不含4、5、6-圈的平面图G,都有b
i(G) ≤ 4?若成立,将同时推广定理2和Gamlath等人的结果。