单圈图的零强迫数的极小值.pdf
《单圈图的零强迫数的极小值.pdf》由会员分享,可在线阅读,更多相关《单圈图的零强迫数的极小值.pdf(8页珍藏版)》请在咨信网上搜索。
1、第36卷第2期2023年6月Vol.36 No.2Jun.2023闽南师范大学学报(自然科学版)Journal of Minnan Normal University(Natural Science)单圈图的零强迫数的极小值涂东鑫(闽南师范大学数学与统计学院,福建 漳州363000)摘要:证明单圈图G满足(G)-2Z(G)P(G)+2,并刻画了满足Z(G)=(G)-2的所有单圈图,其中(G)和P(G)分别表示图G的最大度和悬挂点的数目.关键词:树图;单圈图;最大度;零强迫数中图分类号:O157.5 文献标志码:A 文章编号:2095-7122(2023)02-0042-08Minimum va
2、lues for the zero forcing number of unicyclic graphsTU Dongxin(School of Mathematics and Statistics,Minnan Normal University,Zhangzhou,Fujian 363000,China)Abstract:In this paper,we prove that(G)-2 Z(G)P(G)+2for any unicyclic graphG and that characterize all unicyclic graphs G with Z(G)=(G)-2,where(G
3、)and P(G)denote the maximum degree and the number of pendant vertices of G respectively.Key words:tree;unicyclic graph;maximum degree;zero forcing number考虑的图为简单图.设图G=(V(G)E(G)为n阶简单图,V(G)和E(G)分别为G的顶点集和边集.对于任意uvV(G),eE(G),用dG(v)和NG(v)分别表示顶点v的度和邻域,(G)和(G)分别表示图G的最小度和最大度,dG(uv)表示点u和点v的最短路的边的数目.图G中度数为1的顶点
4、称为悬挂点,用P(G)表示图G中悬挂点的数目.如果dG(v)3,则v称为主顶点.在图G中,如果v,u分别是主顶点和悬挂点,且满足dG(uv)dG(uw),其中w是任意与v不同的主顶点,则u是主顶点v的终点,而v的终点个数称为主顶点v的终度,记为terG(v).如果主顶点的终度是正的,则称主顶点为外部主顶点.连通的无圈图称为树,记为T,用Pn表示一条n个顶点的路.给定图G,染色过程定义如下:用黑、白两种颜色给G的顶点进行染色,设SV(G)是染黑色的顶点集,V(G)-S为染白色的顶点集.若一个黑点v的邻点中只有点u为白色,那么点v强迫点u染成黑色,这个过程称为染色过程.现在从顶点集S出发,反复运用
5、染色过程,最终使得G中所有顶点为黑色,则点集S称为G的一个零强迫集,而零强迫数是G的所有零强迫集中的最小基数,记为Z(G).近期,Oboudi1给出了树中零强迫数的上界和下界,即(T)-1Z(T)P(T)-1,并刻画了满足Z(T)=(T)-1的所有树图.我们注意到任一单圈图可以通过在相应的树上添加一条新边而得到,所以在满足Z(T)=(T)-1的树图上,刻画了满足Z(G)=(G)-2的所有单圈图.收稿日期:2022-10-16基金项目:福建省自然科学基金(2021J02048);福建省教育厅项目(JAT200330)作者简介:涂东鑫(1998),男,广东湛江人,硕士生.涂东鑫:单圈图的零强迫数的
6、极小值第2期1 预备知识首先介绍两类树图:类型类型1 设T(m1mk;n1nk)是图1的(a)所示的树图,其中:mi0ni0,i=1k且k1.类型类型 2 设T(n1nk)是图 1 的(b)所示的树图,其中:ni2i=12k且k1,显然T(n1nk)=T(n1-2nk-2;00).称类型1,类型2的最上层的顶点为根点,且它们的根点只有一个.如图1中的点v和点1分别是它们的根点.如图2所示,该树图的主顶点是v1v2v3v4v6v7,终点是v15v16v17v18v19v20v21v22,其中:v2的终点个数是1,v4v6v7的终点个数分别为2,3和2,v1v3没有终点,所以它的外部主顶点为v2v
7、4v6v7.给出几类特殊的类型1的树图.1)T1=T(m1mk-1;n1nk-20),其中:mi1ni1mk-10i=12k-2.2)T2=T(m1mk-1;n1nk-300),其中:mi0nj0i=12k-1j=12k-3.3)T3=T(m1m2m3;000),其中:mi0i=123.4)T4=T(m1m2m3;n100),其中:mi0n10i=123.通过添加一条新边后得到的3类图形:1)G1表示T1的根点通过一条边连接T3根点的度为2邻点得到的图形;2)G2表示T1的根点通过一条边连接T4的终点得到的图形;3)G3表示T2的根点通过一条边连接T4的任意点得到的图形.(上述所有图类满足Ti
8、的根点是变化后图形Gj的最大度顶点,其中i=12和j=123)vv1v2vk-1vk111111222222333333m1n1m2n2mknk (a)T(m1mk;n1nk)122223333n1n2nk-1nk44445555 (b)T(n1nk)图 1 树图Fig.1 Treev1v3v2v4v5v6v7v8v9v10v11v12v13v14v15v16v17v18v19v20v21v22 图 2 树图TFig.2 Tree T432023年闽南师范大学学报(自然科学版)定理定理11 设T是阶数n2的树图,则(T)-1Z(T)P(T)-1.定理定理21 设T是阶数n3的树图,则Z(T)=
9、(T)-1当且仅当1)T=Pn;2)T=T(m1mk;n1nk-200),其中:mi0nj0i=1kj=1k-2,且k=(T)3.引理引理12 设G是阶数n2的连通图,则1)对任意vV(G),有Z(G-v)-1Z(G)Z(G-v)+1;2)对任意eE(G),有Z(G-e)-1Z(G)Z(G-e)+1.引理1是图的零强迫数的删点删边公式,重复使用以上公式,可得到如下删掉多条边和多个点的公式.推论推论1 设G是阶数n2的连通图,则1)Z(G-i=1kvi)-kZ(G)Z(G-i=1kvi)+k;2)Z(G-i=1kei)-kZ(G)Z(G-i=1kei)+k;3)Z(G-i=1kei-j=1lvj
10、)-(k+l)Z(G)Z(G-i=1kei-j=1lvj)+(k+l)(其中ei与vj是不关联的).引理引理23 设G是阶数为n的连通图,则Z(G)=1当且仅当G=Pn.由上述引理可知,当G是连通图且GPn,则Z(G)2.定理定理34 设T是阶数n2的树图,则Z(T)=(T)当且仅当T为以下之一.1)T=P2;2)T=T(m1mk;n1nk-10),其中:mi1ni1mk0i=12k-1且k=(T)3;3)T=Gi,其中i=123.2 主要结论及其证明单圈图是边数等于顶点数的简单连通图.从树图T的角度构造单圈图,可以在T中添加一条新边eE(T),就可以获得单圈图G.本节不仅证明了单圈图的零强迫
11、数满足(G)-2Z(G)P(G)+2,还刻画了满足Z(G)=(G)-2的所有单圈图.引理引理3 如果图G是通过在一条路Pn上连接一条新边得到的单圈图,则Z(G)=2.证明证明 显然路Pn的左右两个悬挂点是G的一个零强迫集,因此Z(G)2.由于G不是路,结合引理2可得Z(G)2,所以Z(G)=2.定理定理4 设G是一个单圈图,则(G)-2Z(G)P(G)+2.证明证明 先证Z(G)(G)-2.设G是单圈图,e是圈上一条边,T=G-e.结合引理1的2)得Z(G)Z(G-e)-1=Z(T)-1,结合定理1得Z(G)(T)-2.e影响树T的最大度(T)有2种情况:(G)=(T)或者(G)=(T)+1.
12、当(G)=(T),则Z(G)(G)-2.当(G)=(T)+1,则Z(G)(G)-3.断言:Z(G)(G)-3.反证法.假设Z(G)=(G)-3,如果Z(T)(T),则Z(G)(T)-1=(G)-2,这与假设矛盾,从而Z(T)(T)-1.结合定理1得Z(T)=(T)-1.由定理2可得T=Pn(n3)或T=T(m1mk;n1nk-200).其一,当T=Pn(n3),令Pn=v1v2vn,e=vsvt,其中1stn.由于(G)=(T)+1,则e连接Pn的最大度点.当d(vs)=1,d(vt)=2或者d(vs)=d(vt)=2,此时(G)=3.结合引理3可得Z(G)=2,则Z(G)=(G)-1,这与假
13、设矛盾.其二,当T=T(m1mk;n1nk-200),令v是T的最大度顶点,由于(G)=(T)+1,则e有一个端点是v.因为G-v有(T)个Pn,则Z(G)Z(G-v)-1=(T)-1,即Z(G)(G)-2,这与假设矛盾,从而断言成立.因此Z(G)(G)-2.44涂东鑫:单圈图的零强迫数的极小值第2期再证Z(G)P(G)+2.令e=v1v2是圈上的一条边,其中:v1和v2是圈上两个相邻的点.结合引理1的2)得Z(G)Z(G-e)+1=Z(T)+1,再结合定理 1 得Z(G)P(T).下面有 3 种情况:其一,当d(v1)=d(v2)=2,则P(T)=P(G)+2,那么Z(G)P(G)+2.其二
14、,当d(v1)=2d(v2)3,则P(T)=P(G)+1,从而Z(G)P(G)+1.最后,当d(v1)3d(v2)3,则P(T)=P(G),因此Z(G)P(G).综上所述可得Z(G)P(G)+2.证毕.定理定理 5 设G是任意单圈图,Z(G)=(G)-2当且仅当GQi(i=123),其中Q1,Q2和Q3均是由T(m1mk;n1nk-200)(mi0nj0i=1kj=1k-2k2)的根点与其他图形的圈(圈长不小于3)上某一点重合得到图形(见图3).证明证明 必要必要性性 令v是T(m1mk;n1nk-200)的根点,v1v2vk是v不在圈上的邻点和(G)表示图G的最大度.由图可知,(G)=k+2
15、.设v在圈上的邻点分别u1和u2.由于G-v得到k+1个路,根据引理1的1)可得Z(G)Z(G-v)-1k+1-1整理得Z(G)k,则Z(G)(G)-2.在图Q2中,附着在u1的唯一终点记为x1.在图Q3中,附着在u1和u2的唯一终点分别记为x2和y2.在T(m1mk;n1nk-200)中取点集如下:若mi=0,令wi=vi;若mi0,令wi=li,其中li是树的悬挂点使得dT(livi)=mi且i=123k-1,记S=w1w2wk-1.若G=Q1,则Su1是它的一个零强迫集.若G=Q2或G=Q3,则Sx1和Sx2分别是它的一个零强迫集.因此,Z(G)k,即Z(G)(G)-2.综上可得,Z(G
16、)=(G)-2.充分性充分性 设G是一个单圈图,Cn(n3)是G唯一的圈,e是Cn的一条边.令T=G-e,(G)和(T)分别表示G的最大度和T的最大度.假设Z(G)=(G)-2,令=(T).结合引理 1 的 2),可得Z(G)Z(G-e)-1=Z(T)-1.在树T中,e影响树T的最大度有2种情况:(G)=或者(G)=+1.下面凡是对于T(m1,m2,m;n1,n2,n)这类图形,不失一般性地假设mini0(i=12),v是它的最大度点且v1v2v是v的邻点.当(G)=时,显然Z(T)=-1,若不然,Z(T),可得Z(G)Z(T)-1-1,则Z(G)(G)-1,这与假设矛盾.当(G)=+1,则e
17、连接T的最大度顶点.若Z(T)+1,那么Z(G)(G)-1,与假设矛盾.结合定理1,得到-1Z(T),那么Z(T)=-1.若不然,当Z(T)=时,结合定理 3,得到T=G1G2G3(令k=),T=T(m1m2m;n1n2n-10)(n1n-11)或T=P2.当T=Gi(i=123),设v是T的最大度顶点,则G删掉最大度顶点v得到-1条路和一个零强迫数为2的T(m1m2m3;n100),结合引理 1 的 1),可得Z(G)Z(G-v)-1=D-1+2-1=D.由(G)=+1,得到Z(G)(G)-1,与假设矛盾.(1)Q1 (2)Q2 (3)Q3图3 满足Z(G)=(G)-2所有图类Fig.3 A
18、ll graph classes satisfied Z(G)=(G)-2 452023年闽南师范大学学报(自然科学版)当T=T(m1m2m;n1n2n-10)且n1n-11,令e=vx,其中v是T的最大度顶点和x是T上的顶点.T-v的个分支记为Tv1Tv2TvD,那么有2种情况:其一,x是Tv1中的点.其二,x是Tv中的点.如果是x是Tv1中的顶点,则G-v2-v3-v-1得到一个强迫数为2的单圈图和2(-2)条路.根据推论4可得Z(G)Z(G-v2-v3-v-1)-(-2)=2+2(-2)-(-2).整理可得Z(G),则Z(G)(G)-1,这与假设矛盾.如果是x是TvD中的顶点,G-v1-
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 单圈图 强迫 极小
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。