On the Shannon capacity of triangular graphs
type: Item
instance of: scholarly article
title: On the Shannon capacity of triangular graphs
zbMATH Open document ID: 1267.05206
author: Ashik Mathew Kizhakkepallathu
author: Patric Rj Östergård
author: Alexandru Popa
published in: The Electronic Journal of Combinatorics
publication date: 2013-06-07T00:00:00Z
full work available at URL: v20i2p27
review text: 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\).
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 94A24
Mathematics Subject Classification ID: 94A15
zbMATH DE Number: 6171942
zbMATH Keywords: cube packing
zbMATH Keywords: Shannon capacity
zbMATH Keywords: tabu search
zbMATH Keywords: zero-error capacity
describes a project that uses: TABARIS
describes a project that uses: nauty
describes a project that uses: NISPOC
describes a project that uses: Cliquer
describes a project that uses: Tabu search
MaRDI profile type: Publication
cites work: Q5665207
cites work: Q5580172
cites work: A limit theorem for the Shannon capacities of odd cycles I
cites work: On the independence numbers of the cubes of odd cycles
cites work: Q3879234
cites work: TABARIS: An exact algorithm based on tabu search for finding a maximum independent set in a graph
cites work: A user's guide to tabu search
cites work: Tabu search for large scale timetabling problems
cites work: Zero-error information theory
cites work: On the Shannon capacity of a graph
cites work: A covering problem for tori
cites work: Independence numbers of product graphs
cites work: The independence number of the strong product of cycles
cites work: Improved lower bound on the Shannon capacity of \(C_7\)
description: scientific article; zbMATH DE number 6171942