Change search
ReferencesLink to record
Permanent link

Direct link
The guessing number of undirected graph
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
2011 (English)In: The Electronic Journal of Combinatorics, ISSN 1077-8926, Vol. 18, no 1, P192- p.Article in journal (Refereed) Published
Abstract [en]

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.

Place, publisher, year, edition, pages
Atlanta, Ga.: N.J. Calkin and H.S. Wilf , 2011. Vol. 18, no 1, P192- p.
National Category
URN: urn:nbn:se:umu:diva-48464ISI: 000295227000003OAI: diva2:450955
Available from: 2011-10-24 Created: 2011-10-20 Last updated: 2011-10-24Bibliographically approved

Open Access in DiVA

No full text

Search in DiVA

By author/editor
Markström, Klas
By organisation
Department of Mathematics and Mathematical Statistics
In the same journal
The Electronic Journal of Combinatorics

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 47 hits
ReferencesLink to record
Permanent link

Direct link