On the Shannon capacity of triangular graphs
Summary: The Shannon capacity of a graph \(G\) is \(c(G)=\sup_{d\geq 1}(\alpha(G^d))^{\frac{1}{d}},\) where \(\alpha(G)\) is the independence number of \(G\). The Shannon capacity of the Kneser graph \(\mathrm{KG}_{n,r}\) was determined by Lovász 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, \(\overline{\mathrm{KG}}_{n,2}\), is also called the triangular graph \(T_n\). The graph \(T_n\) has the \(n\)-cycle \(C_n\) as an induced subgraph, whereby \(c(T_n) \geq 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 discrete \(d\)-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) \geq \root 3 \of {35} \approx 3.271\), \(c(T_{13}) \geq \root 3 \of {248} \approx 6.283\), \(c(T_{15}) \geq \root 4 \of {2802} \approx 7.276\), and \(c(T_{21}) \geq \root 4 \of {11441} \approx 10.342\).
- A covering problem for tori
- A limit theorem for the Shannon capacities of odd cycles I
- A user's guide to tabu search
- scientific article; zbMATH DE number 3683587 (Why is no real title available?)
- scientific article; zbMATH DE number 3297030 (Why is no real title available?)
- scientific article; zbMATH DE number 3397564 (Why is no real title available?)
- Improved lower bound on the Shannon capacity of C₇
- Independence numbers of product graphs
- On the independence numbers of the cubes of odd cycles
- On the Shannon capacity of a graph
- TABARIS: An exact algorithm based on tabu search for finding a maximum independent set in a graph
- Tabu search for large scale timetabling problems
- The independence number of the strong product of cycles
- Zero-error information theory
This page was built for publication: On the Shannon capacity of triangular graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1953512)
