Abstract: The investigation of the asymptotic behaviour of various graph parameters in powers of a graph is motivated by problems in information theory and extremal combinatorics. Considering various parameters and/or various notions of graph powers we can arrive at different notions of graph capacities, of which the Shannon capacity is best known. Here we study a related notion of the so-called conjunctive capacity of a graph G, CAND(G), introduced and studied by Gargano, Körner and Vaccaro. To determine CAND(G) is a convex programming problem. We show...
(read more)
Topics: 
Combinatorics
Theoretical computer science
Discrete mathematics