Diskretnaya Matematika, Tome 17 (2005) no. 3, pp. 105-108
Citer cet article
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/
@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
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.
[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
