字典积图的任意可分性

Partitioning the Lexicographic Product of Graphs

给定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.