WSEAS Transactions on Mathematics
Print ISSN: 1109-2769, E-ISSN: 2224-2880
Volume 15, 2016
The Vertex Linear Arboricity of Integer Distance Graph G(Dm,1,4)
Authors: , ,
Abstract: An integer distance graph is a graph G(D) with the set Z of all integers as vertex set and two vertices u, v ∈ Z are adjacent if and only if |u − v| ∈ D, where the distance set D is a subset of positive integers. A k-vertex coloring of a graph G is a mapping f from V (G) to [0, k − 1]. A path k-vertex coloring of a graph G is a k-vertex coloring such that every connected component is a path in the induced subgraph of Vi(1 ≤ i ≤ k), where the vertex set Vi is the subset of vertices assigned color i. The vertex linear arboricity of a graph G is the minimum positive integer k such that G has a path k-vertex coloring. In this paper, we studied the vertex linear arboricity of the integer distance graph G(Dm,1,4), where Dm,1,4 = [1,m] | [1, 4], and proved that vla (G(Dm,1,4)) =⌈m/7⌉+1 for every integer m ≥ 6.
Search Articles
Pages: 52-62
WSEAS Transactions on Mathematics, ISSN / E-ISSN: 1109-2769 / 2224-2880, Volume 15, 2016, Art. #6