On the Shannon Capacity of Triangular Graphs

J 2013

On the Shannon Capacity of Triangular Graphs

ASHIK, Mathew Kizhakkepallathu, R. J. Östergård PATRIC and Alexandru POPA

Basic information

Original name

On the Shannon Capacity of Triangular Graphs

Authors

ASHIK, Mathew Kizhakkepallathu, R. J. Östergård PATRIC and Alexandru POPA

Edition

Electronic Journal of Combinatorics, internet, - 2013, 1077-8926

Other information

Language

English

Type of outcome

Článek v odborném periodiku

Field of Study

10000 1. Natural Sciences

Country of publisher

Romania

Confidentiality degree

není předmětem státního či obchodního tajemství

References:

URL

Impact factor

Impact factor: 0.568

Organization unit

Faculty of Informatics

UT WoS

000318848300003

Keywords in English

cube packing; Shannon capacity; tabu search; zero-error capacity

Abstract

V originále

The Shannon capacity of a graph $G$ is defined as $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 $\kg{n}{r}$ was determined by Lov\'{a}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, $\kgc{n}{2}$, has the $n$-cycle $C_n$ as an induced subgraph, whereby $c(\kgc{n}{2}) \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(\kgc{n}{2})$ obtained in this work include $c(\kgc{7}{2}) \geq \sqrt[3]{35} \approx 3.271$, $c(\kgc{13}{2}) \geq \sqrt[3]{248} \approx 6.283$, $c(\kgc{15}{2}) \geq \sqrt[4]{2802} \approx 7.276$, and $c(\kgc{21}{2}) \geq \sqrt[4]{11441} \approx 10.342$.

Links

LG13010, research and development project

Name: Zastoupení ČR v European Research Consortium for Informatics and Mathematics (Acronym: ERCIM-CZ)

Investor: Ministry of Education, Youth and Sports of the CR

Citovat

ASHIK, Mathew Kizhakkepallathu, R. J. Östergård PATRIC and Alexandru POPA. On the Shannon Capacity of Triangular Graphs. Electronic Journal of Combinatorics. internet: -, 2013, vol. 20, No 2, p. P27, 8 pp. ISSN 1077-8926.

@article{1179421,
   author = {Ashik, Mathew Kizhakkepallathu and Patric, R. J. Östergård and Popa, Alexandru},
   article_location = {internet},
   article_number = {2},
   keywords = {cube packing; Shannon capacity; tabu search; zero-error capacity},
   language = {eng},
   issn = {1077-8926},
   journal = {Electronic Journal of Combinatorics},
   title = {On the Shannon Capacity of Triangular Graphs},
   url = {http://www.combinatorics.org/ojs/index.php/eljc/article/view/v20i2p27},
   volume = {20},
   year = {2013}
}

TY  - JOUR
ID  - 1179421
AU  - Ashik, Mathew Kizhakkepallathu - Patric, R. J. Östergård - Popa, Alexandru
PY  - 2013
TI  - On the Shannon Capacity of Triangular Graphs
JF  - Electronic Journal of Combinatorics
VL  - 20
IS  - 2
SP  - P27
EP  - P27
PB  - -
SN  - 10778926
KW  - cube packing
KW  - Shannon capacity
KW  - tabu search
KW  - zero-error capacity
UR  - http://www.combinatorics.org/ojs/index.php/eljc/article/view/v20i2p27
N2  - The Shannon capacity of a graph $G$ is defined as $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 $\kg{n}{r}$ was determined by Lov\'{a}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, $\kgc{n}{2}$, has the $n$-cycle $C_n$ as an induced subgraph, whereby $c(\kgc{n}{2}) \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(\kgc{n}{2})$ obtained in this work include $c(\kgc{7}{2}) \geq \sqrt[3]{35} \approx 3.271$, $c(\kgc{13}{2}) \geq \sqrt[3]{248} \approx 6.283$, $c(\kgc{15}{2}) \geq \sqrt[4]{2802} \approx 7.276$, and $c(\kgc{21}{2}) \geq \sqrt[4]{11441} \approx 10.342$.
ER  -

ASHIK, Mathew Kizhakkepallathu, R. J. Östergård PATRIC and Alexandru POPA. On the Shannon Capacity of Triangular Graphs. \textit{Electronic Journal of Combinatorics}. internet: -, 2013, vol.~20, No~2, p.~P27, 8 pp. ISSN~1077-8926.

Detailed Information on Publication Record