Further results on induced graphoidal decomposition
subject: Graphoidal decomposition; induced graphoidal decomposition; induced graphoidal decomposition number
description: 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.
creator: Hamid I.S.; Joseph M.
source: Discrete Mathematics, Algorithms and Applications, Vol-5, No. 1
publisher: World Scientific Publishing Co. Pte Ltd
date: 2013-01-01
rights: Restricted Access
relation: ISSN: 17938309
format: Online
language: English
type: Article
coverage: Hamid I.S., Department of Mathematics, Madura College, Madurai-11, India; Joseph M., Department of Mathematics, Christ University, Bangalore-29, India