Induced Graphoidal Decompositions in Product Graphs. (20th February 2013)

• Record Type: Journal Article
• Authors: Joseph, Mayamma; Hamid, I. Sahul
• Other Names: De Bonis Annalisa Academic Editor.
• Is Part Of: Journal of discrete mathematics. Volume 2013(2013)
• Publication Date: 2013-02-20
• Subjects: Computer science -- Mathematics -- Periodicals; Computer science -- Mathematics; Periodicals; 511.1
• DOI: 10.1155/2013/892839
• Languages: English
• ISSNs: 2090-9837

Abstract

Abstract : Let G be a nontrivial, simple, finite, connected, and undirected graph. A graphoidal decomposition (GD) of G is a collection ψ of nontrivial paths and cycles in G that are internally disjoint such that every edge of G lies in exactly one member of ψ . By restricting the members of a GD ψ to be induced, the concept of induced graphoidal decomposition (IGD) of a graph has been defined. The minimum cardinality of an IGD of a graph G is called the induced graphoidal decomposition number and is denoted by η i (G ). An IGD of G without any cycles is called an induced acyclic graphoidal decomposition (IAGD) of G, and the minimum cardinality of an IAGD of G is called the induced acyclic graphoidal decomposition number of G, denoted by η i a (G ). In this paper we determine the value of η i (G ) and η i a (G ) when G is a product graph, the factors being paths/cycles.