Acta mathematica scientia,Series A ›› 2010, Vol. 30 ›› Issue (4): 968-983.

• Articles • Previous Articles     Next Articles

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

 ZUO Lian-Cui1, CUI Yu-Quan2, LIU Jia-Zhuang2   

  1. 1.College of Mathematics Science, Tianjin Normal University, Tianjin 300387; 
    2.School of Mathematics |and System Science, Shandong University, Jinan |250100
  • Received:2007-04-18 Revised:2009-09-18 Online:2010-07-25 Published:2010-07-25
  • Supported by:

    天津师范大学引进人才基金(5RL066)资助

Abstract:

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\in Z are adjacent if and only if |u-v in 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))=lm+4/5l  for m≥4 and  va(G(Dm, 2, 2))=lm+1/5l+1 for any positive integer m=10q+j with j =0,1, 2, 3, 5, 6.

Key words: Integer distance graph, Vertex arboricity, Tree coloring

CLC Number: 

  • 05C70
Trendmd