字典积图的任意可分性  

Partitioning the Lexicographic Product of Graphs

作　　者：西日尼阿依·努尔麦麦提 刘凤霞[2] 蔡华 XIRINIAYI Nuermaimaiti;LIU Fengxia;CAI Hua(School of Mathematics and Statistics,Kashgar University,Kashgar Xinjiang 844000,China;School of Mathematics and System Sciences,Xinjiang University,Urumqi Xinjiang 830017,China;School of Mathematics and Data Science,Changji University,Changji Xinjiang 831100,China)

机构地区：[1]喀什大学数学与统计学院,新疆喀什844000 [2]新疆大学数学与系统科学学院,新疆乌鲁木齐830017 [3]昌吉学院数学与数据科学学院,新疆昌吉831100

出　　处：《新疆大学学报（自然科学版中英文）》2024年第2期181-187,共7页Journal of Xinjiang University(Natural Science Edition in Chinese and English)

基　　金：国家自然科学基金“图和有向图的任意可分性的研究”(11961067);新疆维吾尔自治区自然科学基金“图的若干染色问题研究及在数据安全方面的应用”(2022D01C02)。

摘　　要：给定n个顶点的图G,对于满足∑_(i=1)^(k)n_(i)=n的任意一个正整数序列(n_(1),n_(2),…,n_(k)),如果都存在顶点集V(G)的划分(V_(1),V_(2),…,V_(k)),满足Vi导出的子图G[V_(i)]是连通的,并且|V_(i)|=n_(i),其中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是任意可分图.An n-vertex graph G is said to be arbitrarily partitionable(AP,for short),if for any sequence(n_(1),n_(2),…,n_(k))of positive integers such that ∑_(i=1)^(k)n_(i)=n,there exists a partition(V_(1),V_(2),…,V_(k))of vertex set V(G)such that the subgraph G[Vi]induced by Vi is connected and|Vi|=ni for each 1≤i≤k.The lexicographic product of two graphs G and H,denoted by G◦H,has vertex set V(G)×V(H)in which(g,h)(g′,h′)is an edge whenever gg′is an edge in G or g=g′and hh′is an edge in H.In this paper,we mainly discuss the arbitrary partitionability of the lexicographic product of traceable graph and AP graph.We prove that for a tree T of maximum degree at most n+1,if T has a path P such that all the vertices of degree △(T)are in V(P),then the lexicographic product graph T○Pn is AP;if G is a traceable graph and H is an AP graph,then G○H is AP;if G=S(2,a,b)is an AP star-like tree with 2≤a≤b,then G○G is AP;if G is Hamiltonian,H is a graph,then G○H is AP.

关 键 词：图的任意可分性 字典积图 星型树 可迹图 

分 类 号：O157.5[理学—数学]