The Guessing Number of Undirected Graphs
Copyright policy )The Guessing Number of Undirected Graphs
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.
- Umeå University Sweden
Games on graphs (graph-theoretic aspects), Graph theory (including graph drawing) in computer science, Network protocols, Fractional graph theory, fuzzy graph theory, Theory of error-correcting codes and error-detecting codes, protocols for network coding
Games on graphs (graph-theoretic aspects), Graph theory (including graph drawing) in computer science, Network protocols, Fractional graph theory, fuzzy graph theory, Theory of error-correcting codes and error-detecting codes, protocols for network coding
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).11 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Top 10% influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Top 10% impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!