字典积图的任意可分性.pdf
《字典积图的任意可分性.pdf》由会员分享,可在线阅读,更多相关《字典积图的任意可分性.pdf(7页珍藏版)》请在咨信网上搜索。
1、第41卷第2期2024年3月新疆大学学报(自然科学版中英文)Journal of Xinjiang University(Natural Science Edition in Chinese and English)Vol.41,No.2Mar.,2024字典积图的任意可分性西日尼阿依努尔麦麦提1,刘凤霞2,蔡 华3(1.喀什大学 数学与统计学院,新疆 喀什 844000;2.新疆大学 数学与系统科学学院,新疆 乌鲁木齐 830017;3.昌吉学院 数学与数据科学学院,新疆 昌吉 831100)摘要:给定 n 个顶点的图 G,对于满足kPi=1ni=n 的任意一个正整数序列(n1,n2,nk)
2、,如果都存在顶点集 V(G)的划分(V1,V2,Vk),满足 Vi导出的子图 GVi 是连通的,并且|Vi|=ni,其中 1 i k,则称图 G 是任意可分图(简称为 AP).两个图 G 和 H 的字典积图记为 GH,其顶点集为 V(G)V(H),(g,h)(g,h)是 GH 的一条边当且仅当 ggE(G)或者 g=g且 hhE(H).讨论了可迹图和任意可分图的字典积图的任意可分性,证明了对于最大度至多为 n+1 的树 T,如果 T 有一条路 P 满足全部度数为(T)的顶点属于顶点集 V(P),则字典积图 T Pn是任意可分图;如果 G 是一个可迹图且 H 是任意可分图,则图 GH 是任意可分
3、图;如果 G=S(2,a,b)是一个满足 2ab的任意可分星型树,则图 GG 是任意可分图;如果 G 是哈密顿图且 H 是一个图,则 GH 是任意可分图.关键词:图的任意可分性;字典积图;星型树;可迹图DOI:10.13568/ki.651094.651316.2023.11.19.0001中图分类号:O157.5文献标识码:A文章编号:2096-7675(2024)02-0181-07引文格式:西日尼阿依努尔麦麦提,刘凤霞,蔡华 字典积图的任意可分性J 新疆大学学报(自然科学版中英文),2024,41(2):181-187英文引文格式:XIRINIAYI Nuermaimaiti,LIU F
4、engxia,CAI HuaPartitioning the lexicographic product ofgraphsJ Journal of Xinjiang University(Natural Science Edition in Chinese and English),2024,41(2):181-187Partitioning the Lexicographic Product of GraphsXIRINIAYI Nuermaimaiti1,LIU Fengxia2,CAI Hua3(1.School of Mathematics and Statistics,Kashgar
5、 University,Kashgar Xinjiang 844000,China;2.School of Mathematics and System Sciences,Xinjiang University,Urumqi Xinjiang 830017,China;3.School of Mathematics and Data Science,Changji University,Changji Xinjiang 831100,China)Abstract:An n-vertex graph G is said to be arbitrarily partitionable(AP,for
6、 short),if for any sequence(n1,n2,nk)of positive integers such thatkPi=1ni=n,there exists a partition(V1,V2,Vk)of vertex set V(G)such that the subgraph GVi induced by Viis connected and|Vi|=nifor each 1ik.The lexicographic productof two graphs G and H,denoted by GH,has vertex set V(G)V(H)in which(g,
7、h)(g,h)is an edge wheneverggis an edge in G or g=gand hhis an edge in H.In this paper,we mainly discuss the arbitrary partitionabilityof the lexicographic product of traceable graph and AP graph.We prove that for a tree T of maximum degree atmost n+1,if T has a path P such that all the vertices of d
8、egree(T)are in V(P),then the lexicographic productgraph T Pnis AP;if G is a traceable graph and H is an AP graph,then GH is AP;if G=S(2,a,b)is an APstar-like tree with 2ab,then GG is AP;if G is Hamiltonian,H is a graph,then GH is AP.Key words:arbitrary partition ability of graphs;lexicographic produ
9、ct of graphs;star-like trees;traceable graphs0引 言设G=(V,E)是简单的、无向的、n个顶点的图.如果序列=(n1,n2,nk)满足kPi=1ni=n,则称序列收稿日期:2023-11-19基金项目:国家自然科学基金“图和有向图的任意可分性的研究”(11961067);新疆维吾尔自治区自然科学基金“图的若干染色问题研究及在数据安全方面的应用”(2022D01C02)作者简介:西日尼阿依努尔麦麦提(1992),女,硕士,助教,从事图论及其应用的研究,E-mail:通讯作者:刘凤霞(1981),女,博士,教授,主要从事图论及其应用的研究,E-mail
10、:182新疆大学学报(自然科学版中英文)2024年在图G中是可允许的.对于图G的一个可允许序列=(n1,n2,nk),如果存在顶点集V(G)的一个划分(V1,V2,Vk),满足Vi导出的子图GVi是连通的,并且|Vi|=ni对于所有的1ik成立,则称序列是在图G中可实现的.如果图G的每个可允许序列在图G中可实现,则我们把图G称为任意可分图(简称为AP图或AVD图).显然,每个任意可分图必是连通的.任意可分图的研究为平行系统如并行计算机、工作站的网络管理和设计提供理论支持,也是目前国际上非常活跃的领域,但它是一个比较年轻的方向,还有很多问题值得去研究和挖掘.两个顶点不交的图G和H的并记为G H,
11、其顶点集和边集分别为V(G1 G2)=V(G1)V(G2)和E(G1G2)=E(G1)E(G2).两个图G和H的字典积图记为GH,其顶点集为V(G)V(H),(g,h)(g,h)是GH的一条边当且仅当ggE(G)或者g=g且hhE(H).图1给出3K2P3、P42K2和P4(K1K2),图3K2P3是不连通的,图P42K2和P4(K1K2)是连通的.由图1可知,当图G不连通时,图GH也不连通,没必要讨论任意可分性.因此,本文讨论的图G都是连通图.图 1图的字典积任意可分图的一个重要研究方向是与经典问题哈密顿路和完美匹配相结合.含有哈密顿路的图一定是任意可分图,即可迹图必是任意可分图(哈密顿路是
12、指图中一条经过所有顶点且只经过一次的路;如果图G含有哈密顿路,则此图称为可迹图);任意可分图一定有完美匹配或几乎完美匹配,因此一个图含有完美匹配或几乎完美匹配的必要条件是一个图是任意可分图的必要条件.受到广泛关注的是著名的Ore定理,主要是将Ore条件变弱,并结合独立数或完美匹配得出一些结论13.Hor n ak等4证明了对于一个顶点数至少为20的连通图G,如果图G有完美匹配或几乎完美匹配,并且任意两个不相邻的顶点度数之和至少为n5,则图G是任意可分图.Liu等2认为如果图G是一个2K2-free图且(G)=2,则图G是任意可分图当且仅当图G含有完美匹配或几乎完美匹配.Marczyk3结合独立
13、数得到了任意可分图相关的结论:如果图G连通,对于任意不相邻的顶点x,yV(G)满足dG(x)+dG(y)n2且(G)n/2,则图G是任意可分图.本文主要研究字典积图的任意可分性.分别讨论了树T和路Pn、可迹图和任意可分图、圈Cn和树T的字典积图的任意可分性.1树和路的字典积图假设T是树.对于任一顶点uV(T),d(u)表示u的度数.点u和v在树T的距离记作dT(u,v),表示在T中u到v的最短路的长度.为了后面证明方便,下面介绍一个新的图类.两个图G和H的笛卡儿积记为GH,其顶点集V(G)V(H),GH的两个顶点(g,h),(g,h)相邻当且仅当g=g且hhE(H)或者h=h且ggE(G).设
14、V(G)与V(H)分别是两个图G与H的顶点集.如果在V(G)与V(H)的顶点之间存在一个11对应,使得在图G中V(G)的任意两顶点(可以相同)之间恰好有k条边,当且仅当在图H中V(H)的两对应顶点(可以相同)之间恰好有k条边,这里k是非负整数,那么称图G与图H同构,记作G=H.第2期西日尼阿依努尔麦麦提,等:字典积图的任意可分性183定理1对于一个整数n3和最大度为(T)n+1的树T,如果T有一条包含所有度数为(T)的顶点的路,则T Pn是可迹图.证明 假设P=u0u1u2ut是T中包含所有最大度点的最长路.显然,d(u0)=d(ut)=1,d(ui)n对于uiV(T)V(P).为了方便,记V
15、(P)=V0.令s=maxdT(V0,v):v V(T)V0.假设Vi=v|dT(v,V0)=i,v V(T)V0,其中1is.因为T是树且TV0是连通的,对于每个i1,Vi是一个独立集.假设Ti=TiSj=0Vj,0is,得Ts=T且当ij时TjPn是TiPn的子图.下面构造T Pn的一个哈密顿路.步骤1因为V0=u0,u1,u2,ut,T0=TV0且T0Pn是T0Pn的生成子图,所以在T0Pn中找一条哈密顿路P0如下:当t是偶数时,P0=u10u20un10un0un1un11u21u11u12u22un12un2un3un13u2t1u1t1u1tu2tun1tunt.当t是奇数时,P0
16、=u10u20un10un0un1un11u21u11u12u22un12un2un3un13un1t1unt1untun1tu2tu1t.步骤2将T0Pn中的哈密顿路P0扩大到T1Pn中的哈密顿路P1,其中T1=TV0V1.假设V1=S0itui1,ui2,uili是ui(0it)的不在V0中的全部邻点.显然,l0=lt=0且d(ui)=li+2n+1(1it1),故li+1 n.对任意1 i t1,将T0Pn中的路P0中的一部分u1iu2iun1iuni或者uniun1iu2iu1i替换到T1Pn中的路P1i,它的顶点集包含顶点u1i,u2i,un1i,uni和它们在V1中的全部邻点.如果
17、这部分路为u1iu2iun1iuni,则当li=0时P1i=u1iu2iun1iuni,当li 1时,P1i=u1iu1i1u2i1un1i1uni1u2iu1i2u2i2un1i2uni2u3iuliiu1iliu2iliun1iliuniliuli+1iuli+2iuni.因为li+1n,总能得到路P1i.如图2上图所示.如果这部分路为uniun1iu2iu1i,则当li=0时P1i=uniun1iu2iu1i,当li 1时,P1i=uniuni1un1i1 u2i1u1i1un1iuni2un1i2u2i2u1i2un2iunli+1iuniliun1iliu2iliu1iliunlii
- 配套讲稿:
如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。