Guessing Numbers of Odd Cycles

Ross Atkins, Puck Rombach, Fiona Skerman

Research output: Contribution to journalArticle (Academic Journal)peer-review

1 Citation (Scopus)
87 Downloads (Pure)

Abstract

For a given number of colours, s, the guessing number of a graph is the base s logarithm of the size of the largest family of colourings of the vertex set of the graph such that the colour of each vertex can be determined from the colours of the vertices in its neighbourhood. An upper bound for the guessing number of the n-vertex cycle graph Cn is n/2. It is known that the guessing number equals n/2 whenever n is even or s is a perfect square. We show that, for any given integer s≥2, if a is the largest factor of s less than or equal to s√, for sufficiently large odd n, the guessing number of Cn with s colours is (n−1)/2+logs(a). This answers a question posed by Christofides and Markström in 2011.We also present an explicit protocol which achieves this bound for every n. Linking this to index coding with side information, we deduce that the information defect of Cn with s colours is (n+1)/2−logs(a) for sufficiently large odd n.
Original languageEnglish
Article number#P1.45
Number of pages20
JournalElectronic Journal of Combinatorics
Volume24
Issue number1
Early online date3 Mar 2017
Publication statusPublished - Mar 2017

Keywords

  • guessing number
  • graph theory
  • cycle
  • entropy
  • broadcasting with side information
  • combinatorics
  • information theory
  • cycle graph
  • information defect
  • index codes
  • unicast

Fingerprint Dive into the research topics of 'Guessing Numbers of Odd Cycles'. Together they form a unique fingerprint.

Cite this