The Shannon Capacity of Graph Powers
- 3 November 2025
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 72 (1) , 100-111
Abstract
For a graph $G$ , its $k$ -th graph power $G^{k}$ is constructed by placing an edge between two vertices if they are within distance $k$ . We consider the problem of deriving upper bounds on the Shannon capacity of graph powers by using spectral graph theory and linear optimization methods. First, we use the so-called ratio-type bound to provide an alternative and spectral proof of a result by Lovász [IEEE Trans. Inform. Theory 1979], which states that, for a regular graph, the Hoffman ratio bound on the independence number is also an upper bound on the Lovász theta number and, hence, also on the Shannon capacity. In fact, we show that Lovász’ result holds in the more general context of graph powers. Secondly, we derive another bound on the Shannon capacity of graph powers, the so-called rank-type bound, which depends on a new family of polynomials that can be computed by running a simple algorithm. Lastly, we provide several computational experiments that demonstrate the sharpness of the two proposed algebraic bounds. As a by-product, when these two new algebraic bounds are tight, they can be used to easily derive the exact values of the Lovász theta number (which relies on solving an SDP) and the Shannon capacity (which is not known to be computable) of the corresponding graph power.Keywords
All Related Versions
Funding Information
- Dutch Research Council (VI.Vidi.213.085)
- Dutch Research Council (OCENW.KLEIN.475)
- the Agency for Management of University and Research Grants (AGAUR) through the Catalan Government (2021SGR00434)
- the Ministerio de Ciencia, Innovación y Universidades (MICINN) through Spanish Government (PID2020-115442RBI00)
- Universitat Politècnica de Catalunya (AGRUPS-2025)
This publication has 40 references indexed in Scilit:
- The -independence number of -connected graphsApplied Mathematics and Computation, 2021
- Sharp Upper Bounds on the k-Independence Number in Graphs with Given Minimum and Maximum DegreeGraphs and Combinatorics, 2020
- Rainbow Connection Number of Graph Power and Graph ProductsGraphs and Combinatorics, 2013
- Average Degree in Graph PowersJournal of Graph Theory, 2012
- Tree PowersJournal of Algorithms, 1998
- The Shannon Capacity of a UnionCombinatorica, 1998
- On the independence number of sparse graphsRandom Structures & Algorithms, 1995
- Interlacing eigenvalues and graphsLinear Algebra and its Applications, 1995
- Feasibility conditions for the existence of walk-regular graphsLinear Algebra and its Applications, 1980
- Strongly regular graphs with (—1,1,0) adjacency matrix having eigenvalue 3Linear Algebra and its Applications, 1968