On the Shannon Capacity of Triangular Graphs

J 2013

On the Shannon Capacity of Triangular Graphs

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

Základní údaje

Originální název

On the Shannon Capacity of Triangular Graphs

Autoři

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

Vydání

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

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10000 1. Natural Sciences

Stát vydavatele

Rumunsko

Utajení

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

Odkazy

URL

Impakt faktor

Impact factor: 0.568

Organizační jednotka

Fakulta informatiky

UT WoS

000318848300003

Klíčová slova anglicky

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

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 22. 4. 2014 12:30, RNDr. Pavel Šmerk, Ph.D.

Anotace

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$.

Návaznosti

LG13010, projekt VaV

Název: Zastoupení ČR v European Research Consortium for Informatics and Mathematics (Akronym: ERCIM-CZ)

Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Zastoupení ČR v European Research Consortium for Informatics and Mathematics

Citovat

ASHIK, Mathew Kizhakkepallathu, R. J. Östergård PATRIC a Alexandru POPA. On the Shannon Capacity of Triangular Graphs. Electronic Journal of Combinatorics. internet: -, 2013, roč. 20, č. 2, s. P27, 8 s. 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 a Alexandru POPA. On the Shannon Capacity of Triangular Graphs. \textit{Electronic Journal of Combinatorics}. internet: -, 2013, roč.~20, č.~2, s.~P27, 8 s. ISSN~1077-8926.

Podrobný výpis o publikaci