The independence number of the strong product of odd cycles (Q1379990): Difference between revisions
From MaRDI portal
Latest revision as of 11:08, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The independence number of the strong product of odd cycles |
scientific article |
Statements
The independence number of the strong product of odd cycles (English)
0 references
11 August 1998
0 references
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.
0 references
strong product
0 references
odd cycles
0 references
independence number
0 references