Maximum star densities

DOI10.1556/012.2018.55.2.1395MaRDI QIDQ3176667zbMATHOpenAlexFDO

Authors

Publication date 23 July 2018

Published in Studia Scientiarum Mathematicarum Hungarica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1708.01822

zbMATH Keywords

starsgraphonshomomorphism densities

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Enumeration in graph theory (05C30)

Abstract: Given an integer $kgeq2$ and a real number $gammain[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 $kge2$.

Recommendations

• scientific article; zbMATH DE number 4137789
• On the Maximum Induced Density of Directed Stars and Related Problems
• On the number of certain subgraphs contained in graphs with a given number of edges
• Extremal problems of double stars
• The maximum number of edges in a 3-graph not containing a given star

Cited in

(14)

• Ordered and colored subgraph density problems
• On a problem of Ahlswede and Katona
• Minimum dilation stars
• Unified approach to the generalized Turán problem and supersaturation
• MAXIMUM MASS OF A CLASS OF COLD COMPACT STARS
• On the maximum number of copies of H in graphs with given size and order
• A tale of stars and cliques
• The maximum number of edges in a 3-graph not containing a given star
• The feasible region of induced graphs
• The polytope of \(k\)-star densities
• On the number of certain subgraphs contained in graphs with a given number of edges
• On a conjecture of Nagy on extremal densities
• Threshold graphs maximise homomorphism densities
• The inducibility of oriented stars

This page was built for publication: Maximum star densities

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3176667)