|国家预印本平台
首页|Maximizing subgraph density in graphs of bounded degree and clique number

Maximizing subgraph density in graphs of bounded degree and clique number

Maximizing subgraph density in graphs of bounded degree and clique number

来源:Arxiv_logoArxiv
英文摘要

We asymptotically determine the maximum density of subgraphs isomorphic to $H$, where $H$ is any graph containing a dominating vertex, in graphs $G$ on $n$ vertices with bounded maximum degree and bounded clique number. That is, we asymptotically determine the constant $c=c(H,\Delta,\omega)$ such that ex$(n,H,\{K_{1,\Delta+1},K_{\omega+1}\})=(1-o_n(1))cn$. More generally, if $H$ has at least $u$ dominating vertices, then we find the maximum density of subgraphs isomorphic to $H$ in graphs $G$ that have $p$ cliques of size $u$, have bounded clique number, and are $K_u\vee I_{\Delta+1}$-free. For example, we asymptotically determine the constant $d=d(H,\Delta,\omega)$ such that mex$(m,H,\{K_{1,1,\Delta+1},K_{\omega+1}\})=(1-o_m(1))dm$. Then we localize these results, proving a tight inequality involving the sizes of the locally largest cliques and complete split graphs.

Rachel Kirsch

数学

Rachel Kirsch.Maximizing subgraph density in graphs of bounded degree and clique number[EB/OL].(2025-04-14)[2025-07-19].https://arxiv.org/abs/2504.10290.点此复制

评论