Back to Search
Start Over
Maximum star densities
- 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
- Subjects :
- Edge density
General Mathematics
010102 general mathematics
0102 computer and information sciences
Star (graph theory)
01 natural sciences
Combinatorics
Stars
Integer
010201 computation theory & mathematics
FOS: Mathematics
Mathematics - Combinatorics
Combinatorics (math.CO)
0101 mathematics
05C35
MathematicsofComputing_DISCRETEMATHEMATICS
Real number
Mathematics
Subjects
Details
- Language :
- English
- Database :
- OpenAIRE
- Accession number :
- edsair.doi.dedup.....a6d225e5fe6c44fc6ce9f2ddc18e517b