Back to Search Start Over

Maximum star densities

Authors :
Christian Reiher
Stephan Wagner
Publication Year :
2017

Abstract

Given an integer $k \geq 2$ and a real number $\gamma\in [0, 1]$, which graphs of edge density $\gamma$ contain the largest number of $k$-edge stars? For $k=2$ Ahlswede and Katona proved that asymptotically there cannot be more such stars than in a clique or in the complement of a clique (depending on the value of $\gamma$). Here we extend their result to all integers $k\ge 2$.<br />Comment: third version addresses changes arising from the referee reports

Details

Language :
English
Database :
OpenAIRE
Accession number :
edsair.doi.dedup.....a6d225e5fe6c44fc6ce9f2ddc18e517b