Burning Graphs: A Probabilistic Perspective

被引：29

作者：

Mitsche, Dieter ^{[1
]}

Praat, Pawe ^{[2
]}

Roshanbin, Elham ^{[3
]}

机构：

[1] Univ Nice Sophia Antipolis, Lab JA Dieudonne, Parc Valrose, F-06108 Nice 02, France

[2] Ryerson Univ, Dept Math, Toronto, ON, Canada

[3] Dalhousie Univ, Dept Math & Stat, Halifax, NS, Canada

来源：

GRAPHS AND COMBINATORICS | 2017年 / 33卷 / 02期

基金：

加拿大自然科学与工程研究理事会;

关键词：

Random graphs; Random geometric graphs; Burning number; Cartesian product of paths; REGULAR GRAPHS; COPS;

D O I：

10.1007/s00373-017-1768-5

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

In this paper, we study a graph parameter that was recently introduced, the burning number, focusing on a few probabilistic aspects of the problem. The original burning number is revisited and analyzed for binomial random graphs , random geometric graphs, and the Cartesian product of paths. Moreover, new variants of the burning number are introduced in which a burning sequence of vertices is selected according to some probabilistic rules. We analyze these new graph parameters for paths.

引用

页码：449 / 471

页数：23

共 22 条

[1]

Acan H., PODC 2015 IN PRESS

[2] Bootstrap percolation: Visualizations and applications [J].

Adler, J ;

Lev, U .

BRAZILIAN JOURNAL OF PHYSICS, 2003, 33 (03) :641-644

[3]

Alon N., 2008, The Probabilistic Method

[4] CLEANING REGULAR GRAPHS WITH BRUSHES [J].

Alon, Noga ;

Pralat, Pawel ;

Wormald, Nicholas .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2008, 23 (01) :233-250

[5]

[Anonymous], 2003, Oxford studies in probability

[6]

[Anonymous], 2000, WIL INT S D, DOI 10.1002/9781118032718

[7]

[Anonymous], 2001, RANDOM GRAPHS

[8]

Bessy S., 2016, BOUNDS BURNING UNPUB

[9]

Bessy S., 2016, BURNING GRAPH UNPUB

[10] How to Burn a Graph [J].

Bonato, Anthony ;

Janssen, Jeannette ;

Roshanbin, Elham .

INTERNET MATHEMATICS, 2016, 12 (1-2) :85-100

← 1 2 3 →