
تعداد نشریات | 43 |
تعداد شمارهها | 1,685 |
تعداد مقالات | 13,846 |
تعداد مشاهده مقاله | 32,765,789 |
تعداد دریافت فایل اصل مقاله | 12,956,027 |
On label graphoidal covering number-I | ||
Transactions on Combinatorics | ||
مقاله 4، دوره 1، شماره 4، اسفند 2012، صفحه 25-33 اصل مقاله (436.93 K) | ||
نوع مقاله: Research Paper | ||
شناسه دیجیتال (DOI): 10.22108/toc.2012.2271 | ||
نویسندگان | ||
Ismail Sahul Hamid* 1؛ Arumugaperumal Anitha2 | ||
1DEPARTMENT OF MATHEMATICS THE MADURA COLLEGE MADURAI, TAMIL NADU | ||
2Department 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. | ||
کلیدواژهها | ||
Graphoidal labeling؛ Label graphoidal graph؛ Label graphoidal covering number | ||
مراجع | ||
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
| ||
آمار تعداد مشاهده مقاله: 5,754 تعداد دریافت فایل اصل مقاله: 4,284 |