The Fractional Vertex Linear Arboricity of Graphs

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. In this paper, we seek to convert vertex linear arboricity into its fractional analogues, i.e., the fractional vertex linear arboricity of graphs. Let \(\mathbb{Z}_n\) denote the additive group of integers modulo \(n\). Suppose that \(C \subseteq \mathbb{Z}_n \backslash 0\) has the additional property that it is closed under additive inverse, that is, \(-c \in C\) if and only if \(c \in C\). A circulant graph is the graph \(G(\mathbb{Z}_n, C)\) with the vertex set \(\mathbb{Z}_n\) and \(i, j\) are adjacent if and only if \(i – j \in C\). The fractional vertex linear arboricity of the complete \(n\)-partite graph, the cycle \(C_n\), the integer distance graph \(G(D)\) for \(D = \{1, 2, \ldots, m\}\), \(D = \{2, 3, \ldots, m\}\) and \(D = P\) the set of all prime numbers, the Petersen graph and the circulant graph \(G(\mathbb{Z}_a, C)\) with \(C = \{-a + b, \ldots, -b, b, \ldots, a – b\}\) (\(a – 2b \geq b – 3 \geq 3\)) are determined, and an upper and a lower bounds of the fractional vertex linear arboricity of Mycielski graph are obtained.