Commenced in January 2007
Paper Count: 30076
Induced Acyclic Path Decomposition in Graphs
Abstract:A decomposition of a graph G is a collection ψ of graphs H1,H2, . . . , Hr of G such that every edge of G belongs to exactly one Hi. If each Hi is either an induced path in G, then ψ is called an induced acyclic path decomposition of G and if each Hi is a (induced) cycle in G then ψ is called a (induced) cycle decomposition of G. The minimum cardinality of an induced acyclic path decomposition of G is called the induced acyclic path decomposition number of G and is denoted by ¤Çia(G). Similarly the cyclic decomposition number ¤Çc(G) is defined. In this paper we begin an investigation of these parameters.
Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1327466Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1172
 B. D. Acharya and E. Sampathkumar, Graphoidal covers and graphoidal covering number of a graph, Indian J. Pure Appl. Math., 18(10) (1987), 882 - 890.
 S. Arumugam, Path covers in graphs, Lecture Notes of the National Workshop on Decompositions of Graphs and Product Graphs held at Annamalai University, Tamil Nadu, during January 3 - 7, 2006.
 S. Arumugam and I. Sahul Hamid, Simple acyclic graphoidal covers in a graph, Australasian Journal of Combinatorics, 37 (2007), 243 - 255.
 S. Arumugam and I. Sahul Hamid, Simple Graphoidal Covers in a Graph, Journal of Combin. Math. Combin. Comput., 64 (2008), 79 - 95.
 S. Arumugam and I. Sahul Hamid, Simple path covers in a graph, International J. Math. Combin., 3 (2008), 94 - 104.
 S. Arumugam, I. Sahul Hamid and V. M. Abraham, Path decomposition number of a graph, (submitted).
 S. Arumugam and J. Suresh Suseela, Acyclic graphoidal covers and path partitions in a graph, Discrete Math., 190 (1998), 67 - 77.
 G. Chatrand and L. Lesniak, Graphs and Digraphs, Fourth Edition, CRC Press, Boca Raton, 2004.
 F. Harary, Covering and Packing in graphs I, Ann. N. Y. Acad. Sci., 175 (1970), 198 - 205.
 F. Harary and A. J. Schwenk, Evolution of the path number of a graph, covering and packing in graphs II, Graph Theory and Computing, Ed. R. C. Road, Academic Press, New York, (1972), 39 - 45.
 B. Peroche, The path number of some multipartite graphs, Annals of Discrete Math., 9 (1982), 193 - 197.
 I. Sahul Hamid and Abraham V. M., Decomposition of graphs into induced paths and cycles, International Journal of Computational and Mathematical Sciences, 3(7) (2009), 315 - 319.
 R. G. Stanton, D. D. Cowan and L. O. James, Some results on path numbers, Proc. Louisiana Conf. on Combinatorics, Graph Theory and Computing, (1970), 112 - 135.
 Juraj Bosak, Decompositions of Graphs, Kluwer Academic publishers, Dorderecht, The Netherlands, (1990).