整数距离图G(D_(m,k,2))的点荫度

The Vertex Arboricity of Integer Distance Graphs G(D_(m,k,2))

图G的点荫度va(G)是顶点集合V(G)能划分成的这样一些子集的最少数目,其中任一子集的点导出子图都是森林.整数距离图G(D)以全体整数作为顶点集,顶点u,v相邻当且仅当|u-v|∈D,其中D是一个正整数集.对于m>2k≥2,令D_(m,k,2)=[1,m]\{k,2k}.该文得出了整数距离图G(D_(m,k,2))的点荫度的几个上、下界;进而,对于m≥4,有va(G(D_(m,1,2)))=[(m+4)/5];对于m=10q+j,j=0,1,2,3,5,6,有va(G(D_(m,2,2)))=[(m+1)/5]+1.

The vertex arboricity va（G） of a graph G is the minimum number of subsets into which the vertex set V（G） can be partitioned so that each subset induces a subgraph whose connected components are trees. An integer distance graph is a graph G（D） with the set of all integers as vertex set and two vertices u,v∈Z are adjacent if and only if｜u- v｜∈D where the distance set D is a subset of the positive integers set. Let Dm,k,2 = [1, m] ／ {k, 2k} for m 〉 2k 〉 2. In this paper, some upper and lower bounds of the vertex arboricity of the integer distance graph G（Dm, k 2） are obtained. Moreover, va（G（Dm 1 2）） = [-m＋4] for m 〉 4 , , , ,｜ 5｜ -- and va（G（Dm,2,2）） =[ m＋l/5]＋ 1 for any positive integer m = 10q ＋j with j = 0, 1,2,3,5,6.