Discrete Mathematics Group at URI
The faculty of our group is interested in a wide range of areas in discrete mathematics
both pure and applied: graph theory, network theory, extremal and probabilistic methods,
analytic methods, finite model theory, combinatorial games, combinatorial optimization,
bioinformatics applications.
Seminar
Our seminar is held Fridays 1-2pm in Lippitt 204.
Seminar archive.
Speaker | Anthony Bonato, Ryerson University |
Title | Burning spiders and path forests |
Time | Wednesday November 15, 2017, 1-2pm, Lippitt 204 |
Abstract |
Graph burning is a simplified model for the
spread of memes and contagion in social networks. A fire
breaks out in each time-step and spreads to its neighbours.
The burning number of a graph measures the number of
time-steps it takes so that all vertices are burning.
While it is conjectured that the burning number of
a connected graph of order n is a most the ceiling of the
square root of n, this remains open in general. We prove the conjectured bound for spider graphs, which are trees with exactly one vertex of degree at least 3. To prove our result for spiders, we develop new bounds on the burning number for path-forests, which in turn leads to a 3/2-approximation algorithm for computing the burning number of path-forests. Host: Bill Kinnersley |
News
Faculty and their research
Michael Barrus, graph theory
Nancy Eaton,
Associate Dean at the College of Arts and Sciences, graph theory
Barbara Kaskosz, analysis
and its applications to discrete mathematics
William Kinnersley,
graph theory and combinatorial games
Alexandr Kodess, algebraic combinatorics
Lubos Thoma, extremal and probabilistic combinatorics
Doctoral students
Jean Guillaume
John Jones
Eric Peterson
Graduate courses
MTH547 Combinatorics,
MTH548 Graph Theory,
MTH515/516 Algebra,
MTH550 Probability and Stochastic Processes,
MTH656 Probability on Discrete Structures,
CSC541 Advanced Topics in Algorithms,
CSC542 Mathematical Analysis of Algorithms,
CSC544 Theory of Computation,
Special topics courses in Extremal Graph Theory, Ramsey Theory, Algebraic Combinatorics.
Discrete mathematics nearby