Decomposition of Graphs into Induced Paths and Cycles
A decomposition of a graph G is a collection ψ of subgraphs H1,H2, . . . , Hr of G such that every edge of G belongs to exactly one Hi. If each Hi is either an induced path or an induced cycle in G, then ψ is called an induced path decomposition of G. The minimum cardinality of an induced path decomposition of G is called the induced path decomposition number of G and is denoted by πi(G). In this paper we initiate a study of this parameter.
[1] 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.
[2] 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.
[3] S. Arumugam and I. Sahul Hamid, Simple acyclic
graphoidal covers in a graph, Australasian Journal of
Combinatorics, 37 (2007), 243 - 255.
[4] S. Arumugam and I. Sahul Hamid, Simple Graphoidal
Covers in a Graph, Journal of Combin. Math. Combin.
Comput., 64 (2008), 79 - 95.
[5] S. Arumugam and I. Sahul Hamid, Simple path covers
in a graph, International J. Math. Combin., 3 (2008), 94
- 104.
[6] S. Arumugam, I. Sahul Hamid and V. M. Abraham, Path
decomposition number of a graph, (submitted).
[7] S. Arumugam and J. Suresh Suseela, Acyclic graphoidal
covers and path partitions in a graph, Discrete Math., 190
(1998), 67 - 77.
[8] G. Chatrand and L. Lesniak, Graphs and Digraphs,
Fourth Edition, CRC Press, Boca Raton, 2004.
[9] F. Harary, Covering and Packing in graphs I, Ann. N. Y.
Acad. Sci., 175 (1970), 198 - 205.
[10] 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.
[11] B. Peroche, The path number of some multipartite
graphs, Annals of Discrete Math., 9 (1982), 193 - 197.
[12] R. G. Stanton, D. Covan and O. James, Some results on
path numbers, Proc. Louisiana Conf. on Combinatorics,
Graph Theory and Computing, (1970), 112 - 135.
[1] 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.
[2] 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.
[3] S. Arumugam and I. Sahul Hamid, Simple acyclic
graphoidal covers in a graph, Australasian Journal of
Combinatorics, 37 (2007), 243 - 255.
[4] S. Arumugam and I. Sahul Hamid, Simple Graphoidal
Covers in a Graph, Journal of Combin. Math. Combin.
Comput., 64 (2008), 79 - 95.
[5] S. Arumugam and I. Sahul Hamid, Simple path covers
in a graph, International J. Math. Combin., 3 (2008), 94
- 104.
[6] S. Arumugam, I. Sahul Hamid and V. M. Abraham, Path
decomposition number of a graph, (submitted).
[7] S. Arumugam and J. Suresh Suseela, Acyclic graphoidal
covers and path partitions in a graph, Discrete Math., 190
(1998), 67 - 77.
[8] G. Chatrand and L. Lesniak, Graphs and Digraphs,
Fourth Edition, CRC Press, Boca Raton, 2004.
[9] F. Harary, Covering and Packing in graphs I, Ann. N. Y.
Acad. Sci., 175 (1970), 198 - 205.
[10] 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.
[11] B. Peroche, The path number of some multipartite
graphs, Annals of Discrete Math., 9 (1982), 193 - 197.
[12] R. G. Stanton, D. Covan and O. James, Some results on
path numbers, Proc. Louisiana Conf. on Combinatorics,
Graph Theory and Computing, (1970), 112 - 135.
@article{"International Journal of Engineering, Mathematical and Physical Sciences:52185", author = "I. Sahul Hamid and Abraham V. M.", title = "Decomposition of Graphs into Induced Paths and Cycles", abstract = "A decomposition of a graph G is a collection ψ of subgraphs H1,H2, . . . , Hr of G such that every edge of G belongs to exactly one Hi. If each Hi is either an induced path or an induced cycle in G, then ψ is called an induced path decomposition of G. The minimum cardinality of an induced path decomposition of G is called the induced path decomposition number of G and is denoted by πi(G). In this paper we initiate a study of this parameter.
", keywords = "Path decomposition, Induced path decomposition, Induced path decomposition number.", volume = "3", number = "11", pages = "937-5", }
