Geodesic
The guessing number of undirected graphs
The electronic journal of combinatorics, Tome 18 (2011) no. 1

Voir la notice de l'article provenant de la source The Electronic Journal of Combinatorics website

Zbl
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 
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
@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

Cité par Sources :