Guessing numbers of odd cycles

Authors Ross Atkins, Puck Rombach, Fiona Skerman

Publication date 10 April 2017

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1602.03586, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p45

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

cycles entropy guessing number index coding information defect multiple unicast

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38)

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

C_{n}

is

n / 2

. It is known that the guessing number equals

n / 2

whenever

n

is even or

s

is a perfect square cite{Christofides2011guessing}. We show that, for any given integer

s g e q 2

, if

a

is the largest factor of

s

less than or equal to

s q r t s

, for sufficiently large odd

n

, the guessing number of

C_{n}

with

s

colours is

(n - 1) / 2 + l o g_{s} (a)

. This answers a question posed by Christofides and Markstr"{o}m in 2011 cite{Christofides2011guessing}. 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

C_{n}

with

s

colours is

(n + 1) / 2 - l o g_{s} (a)

for sufficiently large odd

n

. Our results are a generalisation of the

s = 2

case which was proven in cite{bar2011index}.

Review text

Summary: 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 \(C_n\) 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 \geq 2\), if \(a\) is the largest factor of \(s\) less than or equal to \(\sqrt{s}\), for sufficiently large odd \(n\), the guessing number of \(C_n\) with \(s\) colours is \((n-1)/2 + \log_s(a)\). This answers a question posed by \textit{D. Christofides} and \textit{K. Markström} [Electron. J. Comb. 18, No. 1, Research Paper P192, 19 p. (2011; Zbl 1337.05077)]. 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 \(C_n\) with \(s\) colours is \((n+1)/2 - \log_s(a)\) for sufficiently large odd \(n\).

Recommendations

Cites work

Cited in

(4)

This page was built for publication: Guessing numbers of odd cycles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q521366)