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\mathrm{\setminus }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,\dots ,m\}$, $D=\{2,3,\dots ,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,\dots ,-b,b,\dots ,a–b\}$ ($a–2b\ge b–3\ge 3$) are determined, and an upper and a lower bounds of the fractional vertex linear arboricity of Mycielski graph are obtained.