第41卷第2期2024年3月新疆大学学报（自然科学版中英文）JournalofXinjiangUniversity(NaturalScienceEditioninChineseandEnglish)Vol.41,No.2Mar.,2024字典积图的任意可分性∗西日尼阿依·努尔麦麦提1，刘凤霞2†，蔡华3(1.喀什大学数学与统计学院，新疆喀什844000；2.新疆大学数学与系统科学学院，新疆乌鲁木齐830017；3.昌吉学院数学与数据科学学院，新疆昌吉831100)摘要：给定n个顶点的图G,对于满足k�i=1ni=n的任意一个正整数序列(n1,n2,···,nk),如果都存在顶点集V(G)的划分(V1,V2,···,Vk),满足Vi导出的子图G[Vi]是连通的,并且|Vi|=ni,其中1≤i≤k,则称图G是任意可分图(简称为AP).两个图G和H的字典积图记为G◦H,其顶点集为V(G)×V(H),(g,h)(g′,h′)是G◦H的一条边当且仅当gg′∈E(G)或者g=g′且hh′∈E(H).讨论了可迹图和任意可分图的字典积图的任意可分性,证明了对于最大度至多为n+1的树T,如果T有一条路P满足全部度数为△(T)的顶点属于顶点集V(P),则字典积图T◦Pn是任意可分图;如果G是一个可迹图且H是任意可分图,则图G◦H是任意可分图;如果G=S(2,a,b)是一个满足2≤a≤b的任意可分星型树,则图G◦G是任意可分图;如果G是哈密顿图且H是一个图,则G◦H是任意可分图.关键词：图的任意可分性;字典积图;星型树;可迹图DOI：10.13568/j.cnki.651094.651316.2023.11.19.0001中图分类号：O157.5文献标识码：A文章编号：2096-7675(2024)02-0181-07引文格式：西日尼阿依·努尔麦麦提，刘凤霞，蔡华．字典积图的任意可分性[J]．新疆大学学报(自然科学版中英文)，2024，41(2)：181-187．英文引文格式：XIRINIAYINuermaimaiti，LIUFengxia，CAIHua．Partitioningthelexicographicproductofgraphs[J]．JournalofXinjiangUniversity(NaturalScienceEditioninChineseandEnglish)，2024，41(2)：181-187．PartitioningtheLexicographicProductofGraphsXIRINIAYINuermaimaiti1,LIUFengxia2,CAIHua3(1.SchoolofMathematicsandStatistics,KashgarUniversity,KashgarXinjiang844000,China;2.SchoolofMathematicsandSystemSciences,XinjiangUniversity,UrumqiXinjiang830017,China;3.SchoolofMathematicsandDataScience,ChangjiUniversity,ChangjiXinjiang831100,China)Abstract：Ann-vertexgraphGissaidtobearbitrarilypartitionable(AP,forshort),ifforanysequence(n1,n2,···,nk)ofpositiveintegerssuchthatk�i=1ni=n,thereexistsapartition(V1,V2,···,Vk...
