The substantial independence number for the strong product of two graphs. (3rd March 2016)

• Record Type: Journal Article
• Authors: Rani Ratha Bai, V.; Robinson Chellathurai, S.; Tamizh Chelvam, T.
• Is Part Of: Journal of discrete mathematical sciences & cryptography. Volume 19:Number 2(2016)
• Page Start: 293
• Page End: 300
• Publication Date: 2016-03-03
• Subjects: Substantial independent set -- Substantial independence number -- Strong product; Computer science -- Mathematics -- Periodicals; Cryptography -- Periodicals; Computer science -- Mathematics; Cryptography; Periodicals; 004.0151
• DOI: 10.1080/09720529.2015.1032539
• Languages: English
• ISSNs: 0972-0529

Abstract

Abstract: Given a graph G, a substantial independent set S is a non empty subset of the vertex set V of the graph G = ( V, E ) if (i) S is an independent set of G and (ii) every vertex in V\S is adjacent to at most one vertex in S . The substantial independence number bS (G) is the maximum cardinality of a maximal substantial independent set. The strong product of two graphs is a graph with V ( G.H ) = V ( G ). V ( H ) and (( g 1, h 1 ) ( g 2, h 2 )) ϵ E ( G.H ) if one of the following holds: g 1 g 2 ϵ E ( G ) and h 1 h 2 ϵ E ( H ) g 1 = g 2 and h 1 h 2 ϵ E ( H ) g 1 g 2 ϵ E ( G ) and h 1 = h 2 In this paper we study the substantial independence number and some bounds for the strong product of two graphs namely Pm . Pn, Cm .Pn and Cm .Cn .