Maximum star densities

DOI10.1556/012.2018.55.2.1395zbMATH Open1399.05130arXiv1708.01822OpenAlexW2745167165MaRDI QIDQ3176667FDOQ3176667

Authors:

Publication date: 23 July 2018

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

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$.

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

Recommendations

• scientific article
• 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

zbMATH Keywords

starsgraphonshomomorphism densities

Mathematics Subject Classification ID

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

Cited In (11)

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

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)