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.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11386/3136603
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 9
  • ???jsp.display-item.citation.isi??? 8
social impact