id: 01121507
dt: j
an: 01121507
au: Vesel, Aleksander; Žerovnik, Janez
ti: The independence number of the strong product of odd cycles.
so: Discrete Math. 182, No.1-3, 333-336 (1998).
py: 1998
pu: Elsevier Science B.V. (North-Holland), Amsterdam
la: EN
cc: 
ut: strong product; odd cycles; independence number
ci: 
li: doi:10.1016/S0012-365X(97)00156-8
ab: 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.
rv: A.Huck (Hannover)