Name
Abstract | ||
|---|---|---|
The Shannon capacity of a graph G is c(G) = sup(d >= 1)(alpha(G(d)))(1/d), where alpha(G) is the independence number of G. The Shannon capacity of the Kneser graph KG(n,r) was determined by Lovasz in 1979, but little is known about the Shannon capacity of the complement of that graph when r does not divide n. The complement of the Kneser graph, (KG) over bar (n,2), is also called the triangular graph T-n. The graph T-n has the n-cycle C-n as an induced subgraph, where by c(T-n) >= c(C-n), and these two families of graphs are closely related in the current context as both can be considered via geometric packings of the discreted-dimensional torus of width n using two types of d-dimensional cubes of width 2. Bounds on c(T-n) obtained in this work include c(T-7) >= (3)root 35 approximate to 3.271, c(T-13) >= (3)root 248 approximate to 6.283, c(T-15 ) >= (4)root 2802 approximate to 7.276, and c(T-21) >= (4)root 11441 approximate to 10.342. |
Year | Venue | Keywords |
|---|---|---|
2013 | ELECTRONIC JOURNAL OF COMBINATORICS | cube packing,Shannon capacity,tabu search,zero-error capacity |
Field | DocType | Volume |
Discrete mathematics,Graph,Independence number,Combinatorics,Induced subgraph,Torus,Shannon capacity of a graph,Kneser graph,Channel capacity,Mathematics | Journal | 20.0 |
Issue | ISSN | Citations |
2.0 | 1077-8926 | 1 |
PageRank | References | Authors |
0.38 | 3 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ashik Mathew Kizhakkepallathu | 1 | 1 | 0.38 |
| Patric R. J. Östergård | 2 | 609 | 70.61 |
| Alexandru Popa | 3 | 70 | 13.34 |