Sperner product is the natural generalization of co-normal product to digraphs. For every class of digraphs closed under Sperner product, the cardinality of the largest subgraph from the given class, contained as an induced subgraph in the co-normal powers of a graph G, has an exponential growth. The corresponding asymptotic exponent is the capacity of G with respect to said class of digraphs. We derive upper and lower bounds for these capacities for various classes of digraphs, and analyze the conditions under which they are tight.
DIFFERENT CAPACITIES OF A DIGRAPH
GALLUCCIO A;
1994
Abstract
Sperner product is the natural generalization of co-normal product to digraphs. For every class of digraphs closed under Sperner product, the cardinality of the largest subgraph from the given class, contained as an induced subgraph in the co-normal powers of a graph G, has an exponential growth. The corresponding asymptotic exponent is the capacity of G with respect to said class of digraphs. We derive upper and lower bounds for these capacities for various classes of digraphs, and analyze the conditions under which they are tight.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.
