The independence number of the strong product of cycles
type: Item
instance of: scholarly article
title: The independence number of the strong product of cycles
zbMATH Open document ID: 0941.05046
DOI: 10.1016/S0898-1221(98)00169-2
publication date: 1999-11-29T00:00:00Z
review text: The strong product of graphs \(G\) and \(H\) is the graph \(G\boxtimes H\) with vertex set \(V(G)\times V(H)\) and \(\{(x_1, x_2), (y_1, y_2)\}\in E(G\boxtimes H)\), whenever either \(x_1y_1\in E(G)\) and \(x_2= y_2\), or \(x_2y_2\in E(H)\) and \(x_1= y_1\), or \(x_1y_1\in E(G)\), \(x_2 y_2\in E(H)\). The author describes algorithms to determine the independence number of two infinite families of graphs: \(C_5\boxtimes C_7\boxtimes C_{2k+1}\) and \(C_5\boxtimes C_9\boxtimes C_{2k+1}\). Applications to the chromatic number of strong products of odd cycles and to the Shannon capacity of \(C_7\) are also discussed.
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 1371540
zbMATH Keywords: independent sets
zbMATH Keywords: independence number
zbMATH Keywords: chromatic number
zbMATH Keywords: strong products of odd cycles
zbMATH Keywords: Shannon capacity
author: Aleksander Vesel
reviewed by: G. Gutin
describes a project that uses: NISPOC
MaRDI profile type: Publication
cites work: On a Problem of C. E. Shannon in Graph Theory
cites work: Numerical invariants and the strong product of graphs
cites work: Independence numbers of product graphs
cites work: A generalized measure of independence and the strong product of graphs
cites work: On the Shannon capacity of a graph
cites work: Analogues of the Shannon Capacity of a Graph
cites work: The independence number of the strong product of odd cycles
cites work: Q4180378
cites work: Q3926600
cites work: Coloring graph products---a survey
cites work: Strong products of \(\chi\)-critical graphs
cites work: Algebraic matching theory
published in: Computers & Mathematics with Applications
description: scientific article; zbMATH DE number 1371540