Podrobný výpis o publikaci

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.

Další formáty: BibTeX LaTeX RIS

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
Originální 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í
WWW	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ěnil	Změnil: RNDr. Pavel Šmerk, Ph.D., učo 3880. Změněno: 22. 4. 2014 12:30.

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

Anotace

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)
LG13010, projekt VaV	Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Zastoupení ČR v European Research Consortium for Informatics and Mathematics