MR
M.J.P. Reinders
info
Please Note
<p>This page displays the records of the person named above and is not linked to a unique person identifier. This record may need to be merged to a profile.</p>
2 records found
1
Degree-Constrained Graph Burning
Extremal Bounds, Regular Constructions, and ๐ผ-Angular Trees
Graph burning is a discrete-time process on a graph that models the spread of information or influence. At each time step, an unburned vertex may be chosen as a source of fire, after which the fire spreads from previously burned vertices to their neighbors. The minimum number of time steps required to burn all vertices is called the burning number ๐(๐บ) of a graph ๐บ.
In many applications, networks are subject to capacity limitations, such as a bounded number of connections per vertex. We study degree-constrained graphs and their extremal behavior.ย
For connected graphs of bounded maximum degree ฮ and a fixed burning number ๐, we determine the maximum possible order. We show that this bound is of order ๐ช(ฮ๐โ1). We also show that this bound is tight via explicit constructions, which yields a logarithmic lower bound of the form ๐(๐บ) โฅ ฮฉ(log_(ฮโ1) ๐). We further show a more narrow bound in the ๐-regular setting and prove this is also tight via explicitย constructions.
We further consider the complementary problem of constructing ๐-regular graphs with large burning numbers. We introduce the family of ๐-necklaces and show that their burning numbers match the known asymptotic upper bound of Martinsson up to an additive constant of one. These graphs also achieve the corresponding upper bound for the radius of Kim et al. up to an additive constant of one.ย
Finally, for restricted tree classes, we obtain improved asymptotic upper bounds on the burning number by adapting an existing framework. One consequence is an asymptotic refinement by a factor of 1/โ2 of the known bound for homeomorphically irreducible trees of Murakami.
Graph burning is a discrete-time process on a graph that models the spread of information or influence. At each time step, an unburned vertex may be chosen as a source of fire, after which the fire spreads from previously burned vertices to their neighbors. The minimum number of time steps required to burn all vertices is called the burning number ๐(๐บ) of a graph ๐บ.
In many applications, networks are subject to capacity limitations, such as a bounded number of connections per vertex. We study degree-constrained graphs and their extremal behavior.ย
For connected graphs of bounded maximum degree ฮ and a fixed burning number ๐, we determine the maximum possible order. We show that this bound is of order ๐ช(ฮ๐โ1). We also show that this bound is tight via explicit constructions, which yields a logarithmic lower bound of the form ๐(๐บ) โฅ ฮฉ(log_(ฮโ1) ๐). We further show a more narrow bound in the ๐-regular setting and prove this is also tight via explicitย constructions.
We further consider the complementary problem of constructing ๐-regular graphs with large burning numbers. We introduce the family of ๐-necklaces and show that their burning numbers match the known asymptotic upper bound of Martinsson up to an additive constant of one. These graphs also achieve the corresponding upper bound for the radius of Kim et al. up to an additive constant of one.ย
Finally, for restricted tree classes, we obtain improved asymptotic upper bounds on the burning number by adapting an existing framework. One consequence is an asymptotic refinement by a factor of 1/โ2 of the known bound for homeomorphically irreducible trees of Murakami.
A Note on Integrity
ILP Modelling and Analysis on Graph Families
This thesis provides a fresh perspective on the (vertex) integrity of graphs, serving as a measure of network robustness. The study begins by introducing fundamental concepts and methods for evaluating the integrity of different graph families. An Integer Linear Programming (ILP) model, specifically designed for assessing integrity, is then presented. By applying this model, integrity values are calculated for various graph families, and patterns within the results are identified. These patterns contribute to establishing boundaries or determining exact values of integrity for the analyzed graph families. The analyzed graph families encompass Glued Paths, generalized Theta graphs, (Double) Cone graphs, Fan graph, Lollipop graphs, generalized Barbell graphs, (Dutch) Windmill graphs, Paley graphs, and Kneser graphs. Additionally, two conjectures are formulated: one concerning a lower bound for the integrity of all Paley graphs, and another addressing the exact integrity values of specific Kneser graphs. The ILP model proves to be a valuable tool for further exploration of graph family integrity, offering opportunities for additional research and expanding our understanding of network robustness.
...
This thesis provides a fresh perspective on the (vertex) integrity of graphs, serving as a measure of network robustness. The study begins by introducing fundamental concepts and methods for evaluating the integrity of different graph families. An Integer Linear Programming (ILP) model, specifically designed for assessing integrity, is then presented. By applying this model, integrity values are calculated for various graph families, and patterns within the results are identified. These patterns contribute to establishing boundaries or determining exact values of integrity for the analyzed graph families. The analyzed graph families encompass Glued Paths, generalized Theta graphs, (Double) Cone graphs, Fan graph, Lollipop graphs, generalized Barbell graphs, (Dutch) Windmill graphs, Paley graphs, and Kneser graphs. Additionally, two conjectures are formulated: one concerning a lower bound for the integrity of all Paley graphs, and another addressing the exact integrity values of specific Kneser graphs. The ILP model proves to be a valuable tool for further exploration of graph family integrity, offering opportunities for additional research and expanding our understanding of network robustness.