On the number of independent sets in damaged Cayley graphs

K. G. Omel'yanov

Diskretnaya Matematika, Tome 17 (2005) no. 3, pp. 105-108

Résumé

The Cayley graph generated by a set $A$ is the graph $\Gamma_{A}(V)$ on a set of positive integers $V$ such that a pair $(u,v)\in V\times V$ is an edge of the graph if and only if $|u-v|\in A$ or $u+v\in A$. We denote by $\mathcal G_2(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 $\Gamma_A(V)$ such that $A=\{\lceil n/2\rceil-t, \lceil n/2\rceil-f\}$, $V\subseteq[\lfloor n/2\rfloor+1,\lfloor n/2\rfloor+t]\cup[n-t+1,n]$, where $n,t,f\in\mathbf N$ and $f$. We also describe the graph with the maximum number of independent sets in the family $\mathcal G_2(n,m)$. This research was supported by the Russian Foundation for Basic Researches, grant 04–01–00359.