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,\ldots,m\} – \{k\}\) for \(m > k \geq 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 \geq 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 \geq 2\).