On the normalized Shannon capacity of a union
Let G 1 × G 2 denote the strong product of graphs G 1 and G 2, that is, the graph on V(G 1) × V(G 2) in which (u 1, u 2) and (v 1, v 2) are adjacent if for each i = 1, 2 we have ui = vi or u i v i E(G i). The Shannon capacity of G is c(G) = limn → α(Gn )1/n, where Gn denotes the n-fold strong power...
| Main Authors: | , |
|---|---|
| Format: | Journal article |
| Published: |
Cambridge University Press
2016
|
| _version_ | 1797061725805084672 |
|---|---|
| author | Keevash, P Long, E |
| author_facet | Keevash, P Long, E |
| author_sort | Keevash, P |
| collection | OXFORD |
| description | Let G 1 × G 2 denote the strong product of graphs G 1 and G 2, that is, the graph on V(G 1) × V(G 2) in which (u 1, u 2) and (v 1, v 2) are adjacent if for each i = 1, 2 we have ui = vi or u i v i E(G i). The Shannon capacity of G is c(G) = limn → α(Gn )1/n, where Gn denotes the n-fold strong power of G, and α(H) denotes the independence number of a graph H. The normalized Shannon capacity of G is Alon [1] asked whether for every < 0 there are graphs G and G satisfying C(G), C(G) < but with C(G + G) > 1 - . We show that the answer is no. |
| first_indexed | 2024-03-06T20:35:22Z |
| format | Journal article |
| id | oxford-uuid:3272dcb8-f603-4564-b91b-d48f90864fd7 |
| institution | University of Oxford |
| last_indexed | 2024-03-06T20:35:22Z |
| publishDate | 2016 |
| publisher | Cambridge University Press |
| record_format | dspace |
| spelling | oxford-uuid:3272dcb8-f603-4564-b91b-d48f90864fd72022-03-26T13:14:06ZOn the normalized Shannon capacity of a unionJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:3272dcb8-f603-4564-b91b-d48f90864fd7Symplectic Elements at OxfordCambridge University Press2016Keevash, PLong, ELet G 1 × G 2 denote the strong product of graphs G 1 and G 2, that is, the graph on V(G 1) × V(G 2) in which (u 1, u 2) and (v 1, v 2) are adjacent if for each i = 1, 2 we have ui = vi or u i v i E(G i). The Shannon capacity of G is c(G) = limn → α(Gn )1/n, where Gn denotes the n-fold strong power of G, and α(H) denotes the independence number of a graph H. The normalized Shannon capacity of G is Alon [1] asked whether for every < 0 there are graphs G and G satisfying C(G), C(G) < but with C(G + G) > 1 - . We show that the answer is no. |
| spellingShingle | Keevash, P Long, E On the normalized Shannon capacity of a union |
| title | On the normalized Shannon capacity of a union |
| title_full | On the normalized Shannon capacity of a union |
| title_fullStr | On the normalized Shannon capacity of a union |
| title_full_unstemmed | On the normalized Shannon capacity of a union |
| title_short | On the normalized Shannon capacity of a union |
| title_sort | on the normalized shannon capacity of a union |
| work_keys_str_mv | AT keevashp onthenormalizedshannoncapacityofaunion AT longe onthenormalizedshannoncapacityofaunion |