Further results on induced graphoidal decomposition
Graphoidal decomposition; induced graphoidal decomposition; induced graphoidal decomposition number
Let G be a nontrivial, simple, finite, connected and undirected graph. A graphoidal decomposition (GD) of G is a collection ? of paths and cycles in G that are internally disjoint such that every edge of G lies in exactly one member of ?. As a variation of GD the notion of induced graphoidal decomposition (IGD) was introduced in [S. Arumugam, Path covers in graphs (2006)] which is a GD all of whose members are either induced paths or induced cycles. The minimum number of elements in such a decomposition of a graph G is called the IGD number, denoted by ?i(G). In this paper, we extend the study of the parameter ?i by establishing bounds for ?i(G) in terms of the diameter, girth and the maximum degree along with characterization of graphs achieving the bounds. 2013 World Scientific Publishing Company.
Discrete Mathematics, Algorithms and Applications, Vol-5, No. 1
Hamid I.S., Department of Mathematics, Madura College, Madurai-11, India; Joseph M., Department of Mathematics, Christ University, Bangalore-29, India