Circulant Digraphs with Larger Linear Guessing Number and Smaller Degree

The guessing number of a digraph is a new invariant in graph theory raised by S. Riis in 2006 and based on its applications in network coding and boolean circuit complexity theory. In this paper, we present the lower and upper bounds on a guessing number and linear guessing number of circulant digraphs by using cyclic codes. As an application of the lower bound, we construct a series of circulant digraphs with a larger linear guessing number and smaller degree. All of these circulant digraphs provide negative answers to S. Riis’ two open problems on the guessing number proposed in [Proceedings of the 2006 4th International Symposium on Modeling and Optimization in Mobile]. We also give a method to construct circulant digraphs with good estimation on their (linear) guessing number from cyclic codes.