2019-03-01
New lower bound on the Shannon capacity of C7 from circular graphs
Publication
Publication
Information Processing Letters , Volume 143 p. 37- 40
We give an independent set of size 367 in the fifth strong product power of C7, where C7 is the cycle on 7 vertices. This leads to an improved lower bound on the Shannon capacity of C7: Θ(C7)≥3671/5>3.2578. The independent set is found by computer, using the fact that the set{t·(1,7,72,73,74)|t∈Z382}⊆Z5382 is independent in the fifth strong product power of the circular graph C108,382. Here the circular graph Ck,n is the graph with vertex set Zn, the cyclic group of order n, in which two distinct vertices are adjacent if and only if their distance (mod n) is strictly less than k.
| Additional Metadata | |
|---|---|
| , , , | |
| doi.org/10.1016/j.ipl.2018.11.006 | |
| Information Processing Letters | |
| Organisation | CWI management |
|
Polak, S., & Schrijver, L. (2019). New lower bound on the Shannon capacity of C7 from circular graphs. Information Processing Letters, 143, 37–40. doi:10.1016/j.ipl.2018.11.006 |
|
