The substantial independence number for the strong product of two graphs

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 b_S (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₁, h₁) (g₂, h₂)) ϵ E(G.H) if one of the following holds:

1. g₁ g₂ ϵ E(G) and h₁ h₂ ϵ E(H)

2. g₁ = g₂ and h₁ h₂ ϵ E(H)

3. g₁ g₂ ϵ E(G) and h₁ = h₂

In this paper we study the substantial independence number and some bounds for the strong product of two graphs namely P_m.P_n, C_m.P_n and C_m.C_n.

Keywords:

• Substantial independent set
• Substantial independence number
• Strong product