- FindStat

edit this statistic or download as text // json

Identifier

St000258: Graphs ⟶ ℤ

Values

([],1) => 1

([],2) => 2

([(0,1)],2) => 2

([],3) => 3

([(1,2)],3) => 2

([(0,2),(1,2)],3) => 2

([(0,1),(0,2),(1,2)],3) => 2

([],4) => 4

([(2,3)],4) => 3

([(1,3),(2,3)],4) => 2

([(0,3),(1,3),(2,3)],4) => 2

([(0,3),(1,2)],4) => 3

([(0,3),(1,2),(2,3)],4) => 2

([(1,2),(1,3),(2,3)],4) => 2

([(0,3),(1,2),(1,3),(2,3)],4) => 2

([(0,2),(0,3),(1,2),(1,3)],4) => 2

([(0,2),(0,3),(1,2),(1,3),(2,3)],4) => 2

([(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)],4) => 2

([],5) => 5

([(3,4)],5) => 4

([(2,4),(3,4)],5) => 3

([(1,4),(2,4),(3,4)],5) => 2

([(0,4),(1,4),(2,4),(3,4)],5) => 2

([(1,4),(2,3)],5) => 3

([(1,4),(2,3),(3,4)],5) => 3

([(0,1),(2,4),(3,4)],5) => 3

([(2,3),(2,4),(3,4)],5) => 3

([(0,4),(1,4),(2,3),(3,4)],5) => 2

([(1,4),(2,3),(2,4),(3,4)],5) => 2

([(0,4),(1,4),(2,3),(2,4),(3,4)],5) => 2

([(1,3),(1,4),(2,3),(2,4)],5) => 3

([(0,4),(1,2),(1,3),(2,4),(3,4)],5) => 2

([(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 2

([(0,4),(1,3),(2,3),(2,4),(3,4)],5) => 2

([(0,4),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 2

([(0,3),(0,4),(1,3),(1,4),(2,3),(2,4)],5) => 2

([(0,3),(0,4),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 2

([(0,4),(1,3),(2,3),(2,4)],5) => 3

([(0,1),(2,3),(2,4),(3,4)],5) => 3

([(0,3),(1,2),(1,4),(2,4),(3,4)],5) => 2

([(0,3),(0,4),(1,2),(1,4),(2,4),(3,4)],5) => 2

([(0,3),(0,4),(1,2),(1,4),(2,3)],5) => 3

([(0,1),(0,4),(1,3),(2,3),(2,4),(3,4)],5) => 2

([(0,3),(0,4),(1,2),(1,4),(2,3),(2,4),(3,4)],5) => 2

([(0,4),(1,2),(1,3),(2,3),(2,4),(3,4)],5) => 2

([(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 2

([(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 2

([(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 2

([(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4)],5) => 2

([(0,2),(0,3),(0,4),(1,2),(1,3),(1,4),(2,4),(3,4)],5) => 2

([(0,2),(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 2

([(0,1),(0,2),(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 2

([],6) => 6

([(4,5)],6) => 5

([(3,5),(4,5)],6) => 4

([(2,5),(3,5),(4,5)],6) => 3

([(1,5),(2,5),(3,5),(4,5)],6) => 2

([(0,5),(1,5),(2,5),(3,5),(4,5)],6) => 2

([(2,5),(3,4)],6) => 4

([(2,5),(3,4),(4,5)],6) => 3

([(1,2),(3,5),(4,5)],6) => 3

([(3,4),(3,5),(4,5)],6) => 4

([(1,5),(2,5),(3,4),(4,5)],6) => 3

([(0,1),(2,5),(3,5),(4,5)],6) => 3

([(2,5),(3,4),(3,5),(4,5)],6) => 3

([(0,5),(1,5),(2,5),(3,4),(4,5)],6) => 2

([(1,5),(2,5),(3,4),(3,5),(4,5)],6) => 2

([(0,5),(1,5),(2,5),(3,4),(3,5),(4,5)],6) => 2

([(2,4),(2,5),(3,4),(3,5)],6) => 3

([(0,5),(1,5),(2,4),(3,4)],6) => 3

([(1,5),(2,3),(2,4),(3,5),(4,5)],6) => 3

([(0,5),(1,5),(2,3),(3,4),(4,5)],6) => 3

([(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 3

([(1,5),(2,4),(3,4),(3,5),(4,5)],6) => 3

([(0,5),(1,5),(2,4),(3,4),(4,5)],6) => 3

([(0,5),(1,5),(2,3),(2,4),(3,5),(4,5)],6) => 2

([(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 2

([(0,5),(1,5),(2,4),(3,4),(3,5),(4,5)],6) => 2

([(0,5),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 2

([(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)],6) => 3

([(0,5),(1,4),(2,4),(2,5),(3,4),(3,5)],6) => 3

([(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)],6) => 2

([(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 2

([(0,5),(1,4),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 2

([(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 2

([(0,4),(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)],6) => 2

([(0,4),(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 2

([(0,5),(1,4),(2,3)],6) => 4

([(1,5),(2,4),(3,4),(3,5)],6) => 3

([(0,1),(2,5),(3,4),(4,5)],6) => 3

([(1,2),(3,4),(3,5),(4,5)],6) => 3

([(0,5),(1,4),(2,3),(3,5),(4,5)],6) => 3

([(1,4),(2,3),(2,5),(3,5),(4,5)],6) => 3

([(0,1),(2,5),(3,4),(3,5),(4,5)],6) => 3

([(0,4),(1,5),(2,3),(2,5),(3,5),(4,5)],6) => 2

([(1,4),(1,5),(2,3),(2,5),(3,5),(4,5)],6) => 2

([(0,5),(1,4),(1,5),(2,3),(2,5),(3,5),(4,5)],6) => 2

([(1,4),(1,5),(2,3),(2,5),(3,4)],6) => 3

([(0,5),(1,4),(2,3),(2,4),(3,5),(4,5)],6) => 3

([(1,2),(1,5),(2,4),(3,4),(3,5),(4,5)],6) => 3

([(0,5),(1,2),(1,4),(2,3),(3,5),(4,5)],6) => 3

>>> Load all 1200 entries. <<<

search for individual values

searching the database for the individual values of this statistic

/ search for generating function

searching the database for statistics with the same generating function

click to show known generating functions

Description

The burning number of a graph.
This is the minimum number of rounds needed to burn all vertices of a graph. In each round, the neighbours of all burned vertices are burnt. Additionally, an unburned vertex may be chosen to be burned.

References

[1] Bonato, A., Janssen, J., Roshanbin, E. How to burn a graph arXiv:1507.06524
[2] Bonato, A., Janssen, J., Roshanbin, E. Burning a Graph as a Model of Social Contagion DOI:10.1007/978-3-319-13123-8_2
[3] Bonato, A., Janssen, J., Roshanbin, E. Burning a graph is hard www.math.ryerson.ca/~abonato/papers/BJR_Burning_ANALCO_Aug11.pdf

Code

def spider_graph(r, s):
    """
    a star with s arms, subdivided into paths with r edges
    """
    G = graphs.StarGraph(s)
    G.subdivide_edges(G.edges(), r-1)
    return G

def burning_number_naive(G, burnt = set([])):
    """
    TESTS:

    Theorem 10 of 'How to burn a graph':
    sage: [burning_number_naive(graphs.PathGraph(k)) - ceil(sqrt(k*1.0)) for k in range(1, 16)]
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

    Corollary 11 of 'How to burn a graph':
    sage: [burning_number_naive(graphs.CycleGraph(k)) - ceil(sqrt(k*1.0)) for k in range(1, 16)]
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

    Lemma 1 of 'Burning a graph is hard':
    sage: [burning_number_naive(spider_graph(1, s)) for s in range(1, 10)]
    [2, 2, 2, 2, 2, 2, 2, 2, 2]

    sage: [burning_number_naive(spider_graph(2, s)) for s in range(1, 10)]
    [2, 3, 3, 3, 3, 3, 3, 3, 3]

    sage: [burning_number_naive(spider_graph(3, s)) for s in range(1, 7)]
    [2, 3, 4, 4, 4, 4]

    sage: [burning_number_naive(spider_graph(4, s)) for s in range(1, 6)]
    [3, 3, 4, 5, 5]

    """
    if len(burnt) == G.num_verts():
        return 0

    for v in list(burnt):
        for u in G[v]:
            burnt.add(u)

    if len(burnt) == G.num_verts():
        return 1

    unburnt = list(set(G.vertices()).difference(burnt))

    # choose in all possible ways an unburnt vertex and burn it
    m = 1 + burning_number_naive(G, burnt.union(set([unburnt[0]])))

    for v in unburnt[1:]:
        m = min(m, 1 + burning_number_naive(G, burnt.union(set([v]))))

    return m
        
def statistic(G):
    return burning_number_naive(G)

Created

Jul 27, 2015 at 15:45 by Martin Rubey

Updated

Jul 27, 2015 at 15:45 by Martin Rubey