Determinação do número de 2-queima para classes de grafos

Abstract

The iterative optimization 2-burning process of a graph G aims to find the minimum number of rounds required to burn all vertices of G. Each vertex of G can be in two states: burned or unburned. The 2-burning process of G begins at round t = 0, in which all vertices start as unburned. Once a vertex is burned, it remains burned until the end of the process. In each round t ≥1, new vertices are burned by performing at least one of the following two operations: (i) choose an unburned vertex to be burned, or (ii) burn any vertex that has at least two burned neighbors from round t −1. The 2-burning number of a graph G is the minimum number of rounds required for all vertices of G to be burned. The 2-burning problem models the real-world issue of information and sentiment dissemination, known as social contagion, where each person is represented by a vertex and the edges represent a friendship relation. In this problem, an individual will only believe a piece of information or gossip if it is confirmed by at least two sources, and will thus spread it after this validation. This work determines tight lower and upper bounds for the 2-burning number of the flower snark, Goldberg snark, and generalized Petersen P(h,2) graph families. Furthermore, an Integer Linear Programming model is proposed for the 2-burning problem, along with a correction to the literature regarding the 2-burning number of the fan graph class.