On label graphoidal covering number-I

Document Type : Research Paper



2 Department of Mathematics Thiagarajar Engineering College Madurai


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 \{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‎ ‎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 2 and (ii) $\eta_l= q$‎. ‎Also‎, ‎we determine the value of label graphoidal covering number for unicyclic graphs‎.


Main Subjects

B. D. Acharya and E. Sampathkumar (1987). Graphoidal covers and graphoidal covering number of a graph. Indian J. Pure Appl. Math.. 18 (10), 882-890 S. Arumugam, B. D. Acharya and E. Sampathkumar (1997). Graphoidal covers of a graph: a creative review. Graph theory and its applications (Tirunelveli, 1996), Tata McGraw-Hill, New Delhi. , 1-28 S. Arumugam and I. Sahul Hamid (2007). Label graphoidal covering number of a graph. Proceedings of the Group Discussion on Labeling of Discrete Structures and Applications, Mary Madha Arts College, Mononthavady, Eds B. D. Acharya, S. Arumugam and A. Rosa; Narosa Publishing House. , 77-82 S. Arumugam and I. Sahul Hamid (2008). Simple path covers in a graph. International J. Math. Combin.. 3, 94-104 S. Arumugam and J. Suresh Suseela (1998). Acyclic graphoidal covers and path partitions in a graph. Discrete Math.. 190, 67-77 O. Favaron and M. Kouider (1988). Path partitions and cycle partitions of Eulerian graphs of maximum degree $4$. Studia Sci. Math. Hungar.. 23, 237-244 J. A. Gallian (1998). A dynamic survey of graph labeling. Electron. J. Combin., Dynamic Survey 6, 43 pp.. 5 F. Harary (1972). Graph Theory. Addision-Wesley, Reading, Mass. F. Harary (1970). Covering and packing in graphs I. Ann. New York Acad. Sci.. 175, 198-205 F. Harary and A. J. Schwenk (1972). Evolution of the path number of a graph. covering and packing in graphs II, Graph Theory and Computing, Ed. R. C. Rad, Academic Press, New York. , 39-45