Guessing games on triangle-free graphs

Peter Jephson Cameron, Anh Dang, Soren Riis

Research output: Contribution to journalArticlepeer-review

8 Citations (Scopus)
1 Downloads (Pure)

Abstract

The guessing game introduced by Riis is a variant of the "guessing your own hats" game and can be played on any simple directed graph G on n vertices. For each digraph G, it is proved that there exists a unique guessing number gn(G) associated to the guessing game played on G. When we consider the directed edge to be bidirected, in other words, the graph G is undirected, Christofides and Markström introduced a method to bound the value of the guessing number from below using the fractional clique cover number kappa_f(G). In particular they showed gn(G) >= |V(G)| - kappa_f(G). Moreover, it is pointed out that equality holds in this bound if the underlying undirected graph G falls into one of the following categories: perfect graphs, cycle graphs or their complement. In this paper, we show that there are triangle-free graphs that have guessing numbers which do not meet the fractional clique cover bound. In particular, the famous triangle-free Higman-Sims graph has guessing number at least 77 and at most 78, while the bound given by fractional clique cover is 50.
Original languageEnglish
Article numberP1.48
Number of pages15
JournalElectronic Journal of Combinatorics
Volume23
Issue number1
Publication statusPublished - 2016

Keywords

  • Network coding
  • Guessing number
  • Clique cover number
  • Higman-Sims graph

Fingerprint

Dive into the research topics of 'Guessing games on triangle-free graphs'. Together they form a unique fingerprint.

Cite this