On label graphoidal covering number-I

Abstract

Let $G=(V‎, ‎E)$ be a graph with $p$ vertices and $q$ edges‎. ‎An <em>acyclic‎ ‎graphoidal cover</em> of $G$ is a collection $psi$ of paths in $G$‎ ‎which are internally-disjoint and cover each edge of the graph‎ ‎exactly once‎. ‎Let $f‎: ‎Vrightarrow {1‎, ‎2‎, ‎ldots‎, ‎p}$ be a bijective‎ ‎labeling of the vertices of $G$‎. ‎Let $uparrow!G_f$ be the‎ ‎directed graph obtained by orienting the edges $uv$ of $G$ from‎ ‎$u$ to $v$ provided $f(u)< f(v)$‎. ‎If the set $psi_f$ of all‎ ‎maximal directed paths in $uparrow!G_f$‎, ‎with directions‎ ‎ignored‎, ‎is an acyclic graphoidal cover of $G$‎, ‎then $f$ is called‎ ‎a emph{graphoidal labeling} of $G$ and $G$ is called a‎ ‎<em>label graphoidal graph</em> and $eta_l=min{|psi_f|‎: ‎f {rm ‎is a graphoidal labeling of} G}$ is called the <em>label‎ ‎graphoidal covering number</em> of $G$‎. ‎In this paper we characterize‎ ‎graphs for which (i) $eta_l=q-m$‎, ‎where $m$ is the number of‎ ‎vertices of degree 2 and (ii) $eta_l= q$‎. ‎Also‎, ‎we determine the value of label graphoidal covering number for unicyclic graphs‎.