Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 2 of 2
Full-Text Articles in Physical Sciences and Mathematics
The Burning Number Of Directed Graphs: Bounds And Computational Complexity, Remie Janssen
The Burning Number Of Directed Graphs: Bounds And Computational Complexity, Remie Janssen
Theory and Applications of Graphs
The burning number of a graph was recently introduced by Bonato et al. Although they mention that the burning number generalizes naturally to directed graphs, no further research on this has been done. Here, we introduce graph burning for directed graphs, and we study bounds for the corresponding burning number and the hardness of finding this number. We derive sharp bounds from simple algorithms and examples. The hardness question yields more surprising results: finding the burning number of a directed tree with one indegree-0 node is NP-hard, but FPT; however, it is W[2]-complete for DAGs. Finally, we give a fixed-parameter …
Note On Rainbow Connection In Oriented Graphs With Diameter 2, Rebecca Holliday, Colton Magnant, Pouria Salehi Nowbandegani
Note On Rainbow Connection In Oriented Graphs With Diameter 2, Rebecca Holliday, Colton Magnant, Pouria Salehi Nowbandegani
Theory and Applications of Graphs
In this note, we provide a sharp upper bound on the rainbow connection number of tournaments of diameter 2. For a tournament Τ of diameter 2, we show 2 ≤ → rc (Τ) ≤ 3. Furthermore, we provide a general upper bound on the rainbow κ-connection number of tournaments as a simple example of the probabilistic method. Finally, we show that an edge-colored tournament of κthdiameter 2 has rainbow κ-connection number at most approximately κ2.