The independence number of the strong product of odd cycles
type: Item
instance of: scholarly article
title: The independence number of the strong product of odd cycles
zbMATH Open document ID: 0893.05007
DOI: 10.1016/S0012-365X(97)00156-8
author: Aleksander Vesel
author: Janez Žerovnik
published in: Discrete Mathematics
publication date: 1998-08-11T00:00:00Z
review text: The strong product \(G\times_sH\) of two graphs \(G\) and \(H\) has vertex set \(V(G)\times V(H)\) and two vertices \((x_1,y_1)\) and \((x_2,y_2)\) are connected by an edge in \(G\times_sH\) if and only if one of the following conditions holds: (i) \(x_1y_1\in E(G)\) and \(x_2= y_2\). (ii) \(x_2y_2\in E(H)\) and \(x_1=y_1\). (iii) \(x_1y_1\in E(G)\) and \(x_2y_2\in E(H)\). In the present paper, the authors investigate the independence number (i.e. the maximal cardinality of a set of pairwise non-adjacent vertices) of strong products of odd cycles. This research was inspired by a work of Shannon on the determination of the zero-error capacity of a noisy channel which turned out to base on such kind of independence numbers. The authors determine the independence number of \(C_5\times_sC_7 \times_sC_7\) \((C_\ell\) denotes a cycle of length \(\ell)\) which turns out to be 23. To obtain this number, they have developed a special software package called NISPOC (Numerical Invariants of Strong Products of Odd Cycles). Also they present lower bounds of the independence numbers for two infinite families of strong products of odd cycles.
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 1121507
zbMATH Keywords: strong product
zbMATH Keywords: odd cycles
zbMATH Keywords: independence number
Wikidata QID: Q114122934
reviewed by: Andreas Huck
MaRDI profile type: Publication
cites work: A generalized measure of independence and the strong product of graphs
cites work: Numerical invariants and the strong product of graphs
cites work: Analogues of the Shannon Capacity of a Graph
cites work: Independence numbers of product graphs
cites work: The independence number of the strong product of cycles
full work available at URL: s0012-365x(97)00156-8
OpenAlex ID: W1966342770
description: scientific article; zbMATH DE number 1121507