Circulant Digraphs with Larger Linear Guessing Number and Smaller Degree

Aixian Zhang () and Keqin Feng
Additional contact information
Aixian Zhang: Department of Mathematical Sciences, Xi’an University of Technology, Xi’an 710048, China
Keqin Feng: Department of Mathematical Sciences, Tsinghua University, Beijing 100084, China

Mathematics, 2025, vol. 13, issue 13, 1-9

Abstract: 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.

Keywords: cyclic codes; guessing number; linear guessing number; circulant digraphs; boolean circuit complexity (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/13/13/2129/pdf (application/pdf)
https://www.mdpi.com/2227-7390/13/13/2129/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:13:y:2025:i:13:p:2129-:d:1690511

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().