Abstract:
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<t<n/4$. 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.
Fulltext:
PDF file (416 kB)