umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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 1097-1440, E-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
Mathematics
Identifiers
URN: urn:nbn:se:umu:diva-48464ISI: 000295227000003OAI: oai:DiVA.org:umu-48464DiVA: diva2:450955
Available from: 2011-10-24 Created: 2011-10-20 Last updated: 2017-12-08Bibliographically 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
Mathematics

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 71 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf