On the Maximum Induced Density of Directed Stars and Related Problems

DOI10.1137/130912931MaRDI QIDQ4979825zbMATH OpenOpenAlexFDO

Authors Hao Huang

Publication date 19 June 2014

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

directed starinducibilityiterated blow-up

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Extremal problems in graph theory (05C35)

Abstract: Let k>=3 be an integer, we prove that the maximum induced density of the k-vertex directed star in a directed graph is attained by an iterated blow-up construction. This confirms a conjecture by Falgas-Ravry and Vaughan, who proved this for k=3, 4. This question provides the first known instance of density problem for which one can prove extremality of an iterated blow-up construction. We also study the inducibility of complete bipartite digraphs and discuss other related problems.

Recommendations

• Optimal packing of induced stars in a graph
• On the exact maximum induced density of almost all graphs and their inducibility
• Bounds on directed star arboricity in some digraph classes
• scientific article; zbMATH DE number 5583535
• On directed labelings of stars
• The polytope of \(k\)-star densities
• Maximum packings and minimum coverings of multigraphs with paths and stars
• On the number of maximal independent sets of vertices in star-like ladders
• Tight concentration of star saturation number in random graphs
• Maximum packings of K_n with k-stars

Cited in

(15)

• On the inducibility of oriented graphs on four vertices
• Inducibility of \(d\)-ary trees
• Rainbow triangles in three-colored graphs
• On the exact maximum induced density of almost all graphs and their inducibility
• On directed labelings of stars
• Maximum star densities
• On the inducibility of cycles
• Stability from graph symmetrisation arguments with applications to inducibility
• The inducibility of oriented stars
• Ordered and colored subgraph density problems
• Inducibility of the net graph
• Inducibility of rainbow graphs
• Inducibility of four-vertex tournaments
• Inducibility of directed paths
• Maximum density of induced 5-cycle is achieved by an iterated blow-up of 5-cycle

This page was built for publication: On the Maximum Induced Density of Directed Stars and Related Problems

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