Other formats:
BibTeX
LaTeX
RIS
@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.
|
