The Vertex Linear Arboricity of a Special Class of Integer Distance Graphs

Abstract

The vertex linear arboricity $vla(G)$ of a nonempty 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.Let $D_{m,k,3}=[1,m]\setminus \{k,2k,3k\}$ for $m\ge 4k\ge 4$. In this paper, we obtain some upper and lower bounds of the vertex linear arboricity of the integer distance graph $G(D_{m,k,3})$ and the exact value of it for some special cases.