Directed burning number
Ars Combinatoria · 15.11.2026 · 168 · 139-148
DOI: 10.61091/ars168-09 ↗Kurz gefasst
Fachartikel in der Zeitschrift Ars Combinatoria, online erschienen am 15.11.2026. Verfasst von Adam Blumenthal und 2 weiteren Autor:innen.
Abstract (Originalsprache)
Let \(G\) be an undirected graph. An orientation \(\vec G\) of \(G\) is a directed graph in which every edge of \(G\) is assigned a direction. Directed graph burning is an iterative graph exploration process in which each round consists of two phases: spreading, then vertex selection. Each vertex is initially considered unburned. In the spreading phase, each burned vertex burns all of its out-neighbors. In the vertex selection phase, a vertex is chosen and burned. The burning number of a directed graph \(b(\vec G)\) is the minimum number of rounds necessary to burn all vertices of \(G\). The orientable burning number of an undirected graph \(G\), denoted \(B(G)\), is the maximum burning number across all orientations of \(G\). In this paper, we prove two main results. First, for any integer \(k\) between the minimum and maximum burning numbers of orientations of \(G\), there exists an orientation \(\vec G\) such that \(b(\vec G) = k\). We also determine the orientable burning number of wheels using a bound on the join of directed graphs.
Zitieren
APA
Blumenthal, A., LaFrankie, Z., & Tripp, M. (2026). Directed burning number. Ars Combinatoria, 168, 139-148. https://doi.org/10.61091/ars168-09
Vancouver
Blumenthal A, LaFrankie Z, Tripp M. Directed burning number. Ars Combinatoria. 2026;168:139-148. doi:10.61091/ars168-09
BibTeX
@article{Blumenthal2026,
author = {Blumenthal, Adam and LaFrankie, Zachary and Tripp, Michael},
title = {Directed burning number},
journal = {Ars Combinatoria},
year = {2026},
volume = {168},
pages = {139--148},
doi = {10.61091/ars168-09}
}
EUVIMED