DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2026.18

Burning Graph Powers and Branching Trees

Authors: Jesper Jansson, Shashanka Kulamarva, Yukihiro Murakami, and Nikolaas Verhulst

Published in: LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026)

Abstract

Graph burning is a discrete-time process that models the spread of social contagion. Initially, all vertices are unburned. In each round, one unburned vertex is selected and burned, while any unburned vertex that has a burned neighbour from the previous round also becomes burned. The burning number of a graph is the minimum number of rounds needed to burn the entire graph. In this paper, we study the burning number of graph powers. First, we show that for a connected graph G, its graph power G^k contains a (k+1)^+-branching tree as a spanning tree. A (k+1)^+-branching tree is one in which all internal vertices have degree at least k+1. We then show that (k+1)^+-branching trees on n vertices have burning number at most ⌈√{4(k-1)n/k²}⌉. As the burning number of a graph is at most the burning number of any of its spanning trees, this gives an upper bound on the burning number of graph powers. We also derive an alternative upper bound on the burning number of k^+-branching trees using the strongest currently known general burning number bound [Bastide et al.]. We then identify the ranges of k and n for which our bound outperforms or matches this alternative bound. Finally, we show that b(G^k) ≤ (1+o(1))√{n/k} based on the asymptotic burning number bound of Norin and Turcotte.

Cite as

Jesper Jansson, Shashanka Kulamarva, Yukihiro Murakami, and Nikolaas Verhulst. Burning Graph Powers and Branching Trees. In 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 386, pp. 18:1-18:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{jansson_et_al:LIPIcs.MFCS.2026.18,
  author =	{Jansson, Jesper and Kulamarva, Shashanka and Murakami, Yukihiro and Verhulst, Nikolaas},
  title =	{{Burning Graph Powers and Branching Trees}},
  booktitle =	{51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026)},
  pages =	{18:1--18:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-442-0},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{386},
  editor =	{Kouck\'{y}, Michal and Petrișan, Daniela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.18},
  URN =		{urn:nbn:de:0030-drops-273990},
  doi =		{10.4230/LIPIcs.MFCS.2026.18},
  annote =	{Keywords: Graph burning, Burning number, Graph power, k^+-branching tree}
}

Document

DOI: 10.4230/LIPIcs.WABI.2023.7

Making a Network Orchard by Adding Leaves

Authors: Leo van Iersel, Mark Jones, Esther Julien, and Yukihiro Murakami

Published in: LIPIcs, Volume 273, 23rd International Workshop on Algorithms in Bioinformatics (WABI 2023)

Abstract

Phylogenetic networks are used to represent the evolutionary history of species. Recently, the new class of orchard networks was introduced, which were later shown to be interpretable as trees with additional horizontal arcs. This makes the network class ideal for capturing evolutionary histories that involve horizontal gene transfers. Here, we study the minimum number of additional leaves needed to make a network orchard. We demonstrate that computing this proximity measure for a given network is NP-hard and describe a tight upper bound. We also give an equivalent measure based on vertex labellings to construct a mixed integer linear programming formulation. Our experimental results, which include both real-world and synthetic data, illustrate the efficiency of our implementation.

Cite as

Leo van Iersel, Mark Jones, Esther Julien, and Yukihiro Murakami. Making a Network Orchard by Adding Leaves. In 23rd International Workshop on Algorithms in Bioinformatics (WABI 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 273, pp. 7:1-7:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{vaniersel_et_al:LIPIcs.WABI.2023.7,
  author =	{van Iersel, Leo and Jones, Mark and Julien, Esther and Murakami, Yukihiro},
  title =	{{Making a Network Orchard by Adding Leaves}},
  booktitle =	{23rd International Workshop on Algorithms in Bioinformatics (WABI 2023)},
  pages =	{7:1--7:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-294-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{273},
  editor =	{Belazzougui, Djamal and Ouangraoua, A\"{i}da},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2023.7},
  URN =		{urn:nbn:de:0030-drops-186333},
  doi =		{10.4230/LIPIcs.WABI.2023.7},
  annote =	{Keywords: Phylogenetics, Network, Orchard Networks, Proximity Measures, NP-hardness}
}

Search Results

Documents authored by Murakami, Yukihiro

Burning Graph Powers and Branching Trees

Abstract

Cite as

Making a Network Orchard by Adding Leaves

Abstract

Cite as

Thanks for your feedback!

Could not send message