On the number of independent sets in damaged Cayley graphs.

The Cayley graph generated by a set A is the graph ΓA(V) on a set of positive integers V such that a pair(u,v) ∈ V×V is an edge of the graph if and only if |u-v| ∈ A or u+v ∈ A. We denote by G2(n,m) the class of graphs G = (V, E) such that G is a union of chains and cycles and |V| = n, |E| = m. In this paper, we present an upper bound for the number of independent sets in Cayley graphs ΓA(V) such that A = {⌈n/2⌉ - t, ⌈n/2⌉ - ƒ}, V &subE; [⌊n/2⌋ + 1, ⌊n/2⌋+t] ∪ [n - t + 1, n], where n, t, ƒ ∈ N and ƒ < t < n/4. We also describe the graph with the maximum number of independent sets in the family g2(n, m). This research was supported by the Russian Foundation for Basic Researches, grant 04–01–00359. [ABSTRACT FROM AUTHOR]