Show simple item record

dc.contributor.authorCameron, PJen_US
dc.contributor.authorDang, ANen_US
dc.contributor.authorRiis, Sen_US
dc.date.accessioned2016-02-05T11:37:35Z
dc.date.accessioned2016-04-18T10:26:56Z
dc.date.submitted2016-04-05T22:29:13.208Z
dc.identifier.urihttp://qmro.qmul.ac.uk/xmlui/handle/123456789/11893
dc.description9 pages, submitted to Electronic Journal of Combinatoric
dc.description9 pages, submitted to Electronic Journal of Combinatoricen_US
dc.description.abstractThe 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 om introduced a method to bound the value of the guessing number from below using the fractional clique number Kf(G). In particular they showed gn(G) >= |V(G)| - Kf(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.en_US
dc.language.isoenen_US
dc.relation.replaceshttp://qmro.qmul.ac.uk/xmlui/handle/123456789/11050
dc.relation.replaces123456789/11050
dc.rightsOriginal article available on arXiv; http://arxiv.org/abs/1410.2405, to be published in http://www.combinatorics.org/
dc.subjectmath.COen_US
dc.subjectmath.COen_US
dc.subjectcs.ITen_US
dc.subjectmath.ITen_US
dc.titleGuessing Games on Triangle-free Graphsen_US
dc.typeArticle
pubs.author-urlhttp://arxiv.org/abs/1410.2405v2en_US
pubs.notesNot knownen_US
pubs.organisational-group/Queen Mary University of London
pubs.organisational-group/Queen Mary University of London/Faculty of Science & Engineering
pubs.organisational-group/Queen Mary University of London/Faculty of Science & Engineering/Electronic Engineering and Computer Science - Staff


Files in this item

Thumbnail
Thumbnail

This item appears in the following Collection(s)

Show simple item record