Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4650066 | Discrete Mathematics | 2009 | 9 Pages |
Abstract
Let DD be a subset of the positive integers. The distance graph G(Z,D)G(Z,D) has all integers as its vertices and two vertices xx and yy are adjacent if and only if |x−y|∈D|x−y|∈D, where the set DD is called distance set . The vertex arboricity va(G)va(G) of a graph GG is the minimum number of subsets into which vertex set V(G)V(G) can be partitioned so that each subset induces an acyclic subgraph. In this paper, the vertex arboricity of graphs G(Z,Dm,k)G(Z,Dm,k) are studied, where Dm,k={1,2,…,m}∖{k}Dm,k={1,2,…,m}∖{k}. In particular, va(G(Dm,1))=⌈m+34⌉ for any integer m≥5m≥5; va(G(Dm,2))=⌈m+14⌉+1 for m=8l+j≥6m=8l+j≥6 and j≠7j≠7, and ⌈m4⌉+1≤va(G(Dm,2))≤⌈m4⌉+2 for m=8l+7m=8l+7.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Lian-Cui Zuo, Qinglin Yu, Jian-Liang Wu,