Geodesic
The guessing number of undirected graphs
The electronic journal of combinatorics, Tome 18 (2011) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

Riis [Electron. J. Combin., 14(1):R44, 2007] introduced a guessing game for graphs which is equivalent to finding protocols for network coding. In this paper we prove upper and lower bounds for the winning probability of the guessing game on undirected graphs. We find optimal bounds for perfect graphs and minimally imperfect graphs, and present a conjecture relating the exact value for all graphs to the fractional chromatic number.
DOI : 10.37236/679
Classification : 05C57, 05C72, 68R10, 68M12, 94B99
Mots-clés : protocols for network coding 
@article{10_37236_679,
     author = {Demetres Christofides and Klas Markstr\"om},
     title = {The guessing number of undirected graphs},
     journal = {The electronic journal of combinatorics},
     year = {2011},
     volume = {18},
     number = {1},
     doi = {10.37236/679},
     zbl = {1337.05077},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/679/}
}
TY  - JOUR
AU  - Demetres Christofides
AU  - Klas Markström
TI  - The guessing number of undirected graphs
JO  - The electronic journal of combinatorics
PY  - 2011
VL  - 18
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/679/
DO  - 10.37236/679
ID  - 10_37236_679
ER  - 
%0 Journal Article
%A Demetres Christofides
%A Klas Markström
%T The guessing number of undirected graphs
%J The electronic journal of combinatorics
%D 2011
%V 18
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/679/
%R 10.37236/679
%F 10_37236_679
Demetres Christofides; Klas Markström. The guessing number of undirected graphs. The electronic journal of combinatorics, Tome 18 (2011) no. 1. doi: 10.37236/679

Cité par Sources :