ON THE LABEL GRAPHOIDAL COVERING NUMBER-II
I. Sahul Hamid, A. Anitha · Discrete Mathematics Algorithms and Applications · 2011
Let G = (V, E) be a graph with p vertices and q edges. An acyclic graphoidal cover of G is a collection ψ of paths in G which are internally disjoint and covering each edge of the graph exactly once. Let f : V → {1, 2, …, p} be a labeling of the vertices of G. Let ↑Gf be the directed graph obtained by orienting the edges uv of G from u to v provided f(u) < f(v). If the set ψf of all maximal directed paths in ↑Gf, with directions ignored, is an acyclic graphoidal cover of G, then f is called a graphoidal labeling of G and G is called a label graphoidal graph and ηl = min {|ψf|: f is a graphoidal labeling of G} is called the label graphoidal covering number of G. An orientation of G in which every vertex of degree greater than 2 is either a sink or a source is a graphoidal orientation. In this paper we characterize graphs for which (i) ηl = ηa and (ii) ηl = Δ. Also, we discuss the relation between graphoidal labeling and graphoidal orientation.