Further results on induced graphoidal decomposition

Title

Further results on induced graphoidal decomposition

Creator

Hamid I.S.; Joseph M.

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.

Source

Discrete Mathematics, Algorithms and Applications, Vol-5, No. 1

Date

2013-01-01

Publisher

World Scientific Publishing Co. Pte Ltd

Subject

Graphoidal decomposition; induced graphoidal decomposition; induced graphoidal decomposition number

Coverage

Hamid I.S., Department of Mathematics, Madura College, Madurai-11, India; Joseph M., Department of Mathematics, Christ University, Bangalore-29, India

Rights

Restricted Access

Relation

ISSN: 17938309

Format

Online

Language

English

Type

Article

Identifier

https://doi.org/10.1142/S1793830913500067

https://www.scopus.com/inward/record.uri?eid=2-s2.0-85061326897&doi=10.1142%2fS1793830913500067&partnerID=40&md5=362af9d35584a8148e44180ef7e46234