Graphs with average degree smaller than 3011 burn slowly

DOI10.1007/S00373-012-1265-9MaRDI QIDQ742585zbMATH OpenOpenAlexFDO

Authors Paweł Prałat

Publication date 19 September 2014

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00373-012-1265-9

zbMATH Keywords

random graphssurviving ratefirefighter

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Games on graphs (graph-theoretic aspects) (05C57)

Recommendations

• Sparse graphs are not flammable
• The surviving rate of a graph for the firefighter problem
• The edge surviving rate of a class of planar graphs for the firefighter problem
• The 2-surviving rate of planar graphs with average degree lower than \(\frac{9}{2}\)
• Surviving rates of graphs with bounded treewidth for the firefighter problem

Cites work

• scientific article; zbMATH DE number 3904630 (Why is no real title available?)
• scientific article; zbMATH DE number 53883 (Why is no real title available?)
• scientific article; zbMATH DE number 1342092 (Why is no real title available?)
• scientific article; zbMATH DE number 1506515 (Why is no real title available?)
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• A proof of alon's second eigenvalue conjecture
• Expander graphs and their applications
• Explicit construction of linear sized tolerant networks
• Firefighting on trees: How bad is the greedy algorithm?
• Sparse graphs are not flammable
• Surviving rates of graphs with bounded treewidth for the firefighter problem
• The Firefighter problem: a survey of results, directions and questions
• The firefighter problem for graphs of maximum degree three
• The surviving rate of a graph for the firefighter problem
• The surviving rate of an infected network
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators

Cited in

(12)

• Surviving rate of graphs and firefighter problem
• Planar graph is on fire
• Asymptotic surviving rate of trees with multiple fire sources
• Firefighting as a strategic game
• The surviving rate of a graph for the firefighter problem
• Sparse graphs are not flammable
• The firefighter problem: empirical results on random graphs
• A lower bound of the surviving rate of a planar graph with girth at least seven
• Fighting constrained fires in graphs
• Burning graphs: a probabilistic perspective
• Firefighting on square, hexagonal, and triangular grids
• The surviving rate of planar graphs without short cycles

This page was built for publication: Graphs with average degree smaller than \(\frac{30}{11}\) burn slowly

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