The Shannon capacity of every induced subgraph of a perfect graph equals its clique number. However, for the co--normal powers of an odd cycle the super--multiplicativity of the clique number makes the determination of capacity one of the hardest problems in combinatorics. We study the asymptotic growth of induced subgraphs of some particular type in powers of a fixed graph. In case of a simple graph we investigate the asymptotic growth in its co--normal powers of the largest induced subgraph on which non--adjacency is an equivalence relation, (equivalence graphs). For directed graphs we introduce a natural generalization of the co--normal product called Sperner product and analyze the directed version of the problem of asymptotic growth both for the clique number (Sperner capacity) and for induced subgraphs corresponding to equivalence--subgraphs with a particular direction of their edges, called waterfalls.
Different capacities of a digraph
GARGANO, Luisa;
1994-01-01
Abstract
The Shannon capacity of every induced subgraph of a perfect graph equals its clique number. However, for the co--normal powers of an odd cycle the super--multiplicativity of the clique number makes the determination of capacity one of the hardest problems in combinatorics. We study the asymptotic growth of induced subgraphs of some particular type in powers of a fixed graph. In case of a simple graph we investigate the asymptotic growth in its co--normal powers of the largest induced subgraph on which non--adjacency is an equivalence relation, (equivalence graphs). For directed graphs we introduce a natural generalization of the co--normal product called Sperner product and analyze the directed version of the problem of asymptotic growth both for the clique number (Sperner capacity) and for induced subgraphs corresponding to equivalence--subgraphs with a particular direction of their edges, called waterfalls.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
