An n-vertex graph G is said to be arbitrarily partitionable(AP,for short),if for any sequence(n1,n2,…,nk)of positive integers such that kΣi=1 ni=n,there exists a partition(V1,V2,…,Vk)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(o)H,has vertex set V(G)x 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(o)Pn is AP;if G is a traceable graph and H is an AP graph,then G(o)H is AP;if G=S(2,a,b)is an AP star-like tree with 2 ≤ a ≤ b,then G(o)G is AP;if G is Hamiltonian,H is a graph,then G(o)H is AP.
关键词
图的任意可分性/字典积图/星型树/可迹图
Key words
arbitrary partition ability of graphs/lexicographic product of graphs/star-like trees/traceable graphs
维普
万方数据