Geodesic
On the number of independent sets in damaged Cayley graphs
Diskretnaya Matematika, Tome 17 (2005) no. 3, pp. 105-108
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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. 
@article{DM_2005_17_3_a9,
     author = {K. G. Omel'yanov},
     title = {On the number of independent sets in damaged {Cayley} graphs},
     journal = {Diskretnaya Matematika},
     pages = {105--108},
     year = {2005},
     volume = {17},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2005_17_3_a9/}
}
TY  - JOUR
AU  - K. G. Omel'yanov
TI  - On the number of independent sets in damaged Cayley graphs
JO  - Diskretnaya Matematika
PY  - 2005
SP  - 105
EP  - 108
VL  - 17
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/DM_2005_17_3_a9/
LA  - ru
ID  - DM_2005_17_3_a9
ER  - 
%0 Journal Article
%A K. G. Omel'yanov
%T On the number of independent sets in damaged Cayley graphs
%J Diskretnaya Matematika
%D 2005
%P 105-108
%V 17
%N 3
%U http://geodesic.mathdoc.fr/item/DM_2005_17_3_a9/
%G ru
%F DM_2005_17_3_a9
K. G. Omel'yanov. On the number of independent sets in damaged Cayley graphs. Diskretnaya Matematika, Tome 17 (2005) no. 3, pp. 105-108. http://geodesic.mathdoc.fr/item/DM_2005_17_3_a9/

[1] Alon N., “Independent sets in regular graphs and sum-free subsets of finite groups”, Israel J. Math., 73:2 (1991), 247–256 | DOI | MR | Zbl

[2] Omelyanov K. G., Sapozhenko A. A., “O chisle mnozhestv, svobodnykh ot summ, v otrezke naturalnykh chisel”, Diskretnaya matematika, 14:3 (2002), 3–7 | MR

[3] Omelyanov K. G., Sapozhenko A. A., “O chisle i strukture mnozhestv, svobodnykh ot summ, v otrezke naturalnykh chisel”, Diskretnaya matematika, 15:4 (2003), 141–147 | MR

[4] Sapozhenko A. A., “Dokazatelstvo gipotezy Kamerona–Erdesha o chisle mnozhestv, svobodnykh ot summ”, Matem. voprosy kibernetiki, 12 (2003), 5–14

[5] Green B., “The Cameron–Erdős conjecture”, Bull. London Math. Soc., 36:6 (2004), 769–778 | DOI | MR | Zbl