The Vertex Linear Arboricity of an Integer Distance Graph with a Special Distance Set

Abstract

The vertex linear arboricity $vla(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 paths. 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 $D_{m,k}=\{1,2,\dots ,m\}–\{k\}$ for $m>k\ge 1$. In this paper, some upper and lower bounds of the vertex linear arboricity of the integer distance graph $G(D_{m,k})$ are obtained. Moreover, $vla(G(D_{m,1}))=\lceil \frac{m}{4}\rceil +1$ for $m\ge 3$, $vla(G(D_{8l+1,2}))=2l+2$ for any positive integer $l$ and $vla(G(D_{4q,2}))=q+2$ for any integer $q\ge 2$.