Maximum induced forests in random graphs

DOI10.1016/J.DAM.2021.08.018MaRDI QIDQ2235276zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 21 October 2021

Published in Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

random graphconcentrationinduced treeinduced forest

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Extremal problems in graph theory (05C35)

Abstract: We prove that with high probability maximum sizes of induced forests in dense binomial random graphs are concentrated in two consecutive values.

Recommendations

• On the order of the largest induced tree in a random graph
• Trees in random graphs
• Induced Forests in Regular Graphs with Large Girth
• Forests in random graphs
• scientific article; zbMATH DE number 4087713

Cites work

• scientific article; zbMATH DE number 932179 (Why is no real title available?)
• scientific article; zbMATH DE number 3340110 (Why is no real title available?)
• A Remark on Stirling's Formula
• Amazing and aesthetic aspects of analysis
• Cliques in random graphs
• Maximal induces trees in sparse random graphs
• Maximum sparse induced subgraphs of the binomial random graph with given number of edges
• On colouring random graphs
• On induced paths, holes and trees in random graphs
• On the order of the largest induced tree in a random graph

Cited in

(13)

• Forests in random graphs
• Induced forests in some distance-regular graphs
• Indistinguishability of the components of random spanning forests
• On maximum induced forests in graphs
• The analysis of a prioritised probabilistic algorithm to find large induced forests in regular graphs with large girth
• The maximum size of an induced forest in the binomial random graph
• Maximum induced forests in graphs of bounded treewidth
• Induced forests and trees in Erdős-Rényi random graph
• Maximum induced trees in sparse random graphs
• scientific article; zbMATH DE number 4087713 (Why is no real title available?)
• MIP formulations for induced graph optimization problems: a tutorial
• Induced Forests in Regular Graphs with Large Girth
• Maximal induces trees in sparse random graphs

This page was built for publication: Maximum induced forests in random graphs

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