Abstract | ||
---|---|---|
Given a fixed graph $H$ that embeds in a surface $\Sigma$, what is the maximum number of copies of $H$ in an $n$-vertex graph $G$ that embeds in $\Sigma$? We show that the answer is $\Theta(n^{f(H)})$, where $f(H)$ is a graph invariant called the `flap-number' of $H$, which is independent of $\Sigma$. This simultaneously answers two open problems posed by Eppstein (1993). When $H$ is a complete graph we give more precise answers. |
Year | DOI | Venue |
---|---|---|
2022 | 10.1017/S0963548321000560 | Combinatorics, Probability & Computing |
DocType | Volume | Issue |
Journal | 31 | 5 |
ISSN | Citations | PageRank |
0963-5483 | 0 | 0.34 |
References | Authors | |
0 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Tony Huynh | 1 | 11 | 9.36 |
Gwenaël Joret | 2 | 196 | 28.64 |
David R. Wood | 3 | 1073 | 96.22 |