On label graphoidal covering number-I

Let G=(V‎, ‎E) be a graph with p vertices and q edges‎. ‎An acyclic‎ ‎graphoidal cover 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‎: ‎V\rightarrow \{۱‎, ‎۲‎, ‎\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‎ ‎label graphoidal graph and \eta_l=\min\{|\psi_f|‎: ‎f \ {\rm ‎is\ a\ graphoidal\ labeling\ of}\ G\} is called the label‎ ‎graphoidal covering number of G‎. ‎In this paper we characterize‎ ‎graphs for which (i) \eta_l=q-m‎, ‎where m is the number of‎ ‎vertices of degree ۲ and (ii) \eta_l= q‎. ‎Also‎, ‎we determine the value of label graphoidal covering number for unicyclic graphs‎.

Keywords:

Graphoidal labeling , Label graphoidal graph , Label graphoidal covering number