K. G. Omelyanov
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 (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 ⫅ [?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 (n, m).
Discrete Mathematics and Applications, Walter de Gruyter
Print ISSN: 0924-9266
Volume: 15, 05/2005
Pages: 361 - 364
Show full article (external site)
Show all available items of this journal
Search
