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 graphG, has an exponential growth. The corresponding asymptotic exponent is the capacity ofG 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. |
Year | DOI | Venue |
---|---|---|
1994 | 10.1007/BF02986655 | Graphs and Combinatorics |
Keywords | Field | DocType |
upper and lower bounds,exponential growth | Discrete mathematics,Combinatorics,Exponent,Upper and lower bounds,Bipartite graph,Induced subgraph,Cardinality,Directed graph,Mathematics,Digraph,Exponential growth | Journal |
Volume | Issue | ISSN |
10 | 2-4 | 1435-5914 |
Citations | PageRank | References |
4 | 0.56 | 7 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Anna Galluccio | 1 | 193 | 23.05 |
Luisa Gargano | 2 | 725 | 71.91 |
János Körner | 3 | 4 | 0.56 |
Gábor Simonyi | 4 | 249 | 29.78 |