Name
Abstract | ||
|---|---|---|
For a graph property X, let X"n be the number of graphs with vertex set {1,...,n} having property X, also known as the speed of X. A property X is called factorial if X is hereditary (i.e. closed under taking induced subgraphs) and n^c^"^1^n@?X"n@?n^c^"^2^n for some constants c"1 and c"2. Hereditary properties with speed slower than factorial are surprisingly well structured. The situation with factorial properties is more complicated and less explored. Only the properties with speeds up to the Bell number are well studied and well behaved. To better understand the behavior of factorial properties with faster speeds we introduce a structural tool called locally bounded coverings and show that a variety of graph properties can be described by means of this tool. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1016/j.ejc.2011.10.006 | Eur. J. Comb. |
Keywords | Field | DocType |
bounded covering,graph property,property x,bell number,graph property x,induced subgraphs,hereditary property,structural tool,faster speed,factorial property | Discrete mathematics,Graph,Combinatorics,Bell number,Graph property,Vertex (geometry),Factorial,Mathematics,Bounded function | Journal |
Volume | Issue | ISSN |
33 | 4 | 0195-6698 |
Citations | PageRank | References |
4 | 0.45 | 15 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Vadim V. Lozin | 1 | 947 | 83.65 |
| Colin Mayhill | 2 | 12 | 2.00 |
| Victor Zamaraev | 3 | 18 | 9.64 |