Given a fixed graph H that embeds in a surface Σ , what is the maximum number of copies of H in an n-vertex graph G that embeds in Σ ? We show that the answer is Θ(𝑛𝑓(𝐻)) , where f(H) is a graph invariant called the ‘flap-number’ of H, which is independent of Σ . This simultaneously answers two open problems posed by Eppstein ((1993) J. Graph Theory17(3) 409–416.). The same proof also answers the question for minor-closed classes. That is, if H is a 𝐾3,𝑡 minor-free graph, then the maximum number of copies of H in an n-vertex 𝐾3,𝑡 minor-free graph G is Θ(𝑛𝑓′(𝐻)) , where f′(H) is a graph invariant closely related to the flap-number of H. Finally, when H is a complete graph we give more precise answers.
SUBGRAPH DENSITIES in A SURFACE / Huynh, T.; Joret, G.; Wood, D. R.. - In: COMBINATORICS, PROBABILITY AND COMPUTING. - ISSN 1469-2163. - (2020).
SUBGRAPH DENSITIES in A SURFACE
Huynh, T.;Joret, G.;
2020
Abstract
Given a fixed graph H that embeds in a surface Σ , what is the maximum number of copies of H in an n-vertex graph G that embeds in Σ ? We show that the answer is Θ(𝑛𝑓(𝐻)) , where f(H) is a graph invariant called the ‘flap-number’ of H, which is independent of Σ . This simultaneously answers two open problems posed by Eppstein ((1993) J. Graph Theory17(3) 409–416.). The same proof also answers the question for minor-closed classes. That is, if H is a 𝐾3,𝑡 minor-free graph, then the maximum number of copies of H in an n-vertex 𝐾3,𝑡 minor-free graph G is Θ(𝑛𝑓′(𝐻)) , where f′(H) is a graph invariant closely related to the flap-number of H. Finally, when H is a complete graph we give more precise answers.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
