EUVIMEDEUVIMED entdecken
Crossref

Illuminating a Graph

Wayne Goddard, Deirdre LaVey

Ars Combinatoria · 2024

DOI: 10.61091/ars-60-03 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Ars Combinatoria, 2024. Verfasst von Wayne Goddard und 1 weiteren Autor:innen.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We introduce a two-player game where the goal is to illuminate all edges of a graph. At each step the first player, called Illuminator, taps a vertex. The second player, called Adversary, reveals the edges incident with that vertex (consistent with the edges incident with the already tapped vertices). Illuminator tries to minimize the taps needed, and the value of the game is the number of taps needed with optimal play. We provide bounds on the value in trees and general graphs. In particular, we show that the value for the path on n vertices is 2 3 n + O ( 1 ) , and there is a constant ε > 0 such that for every caterpillar on n vertices, the value is at most ( 1 – ε ) n + 1 .

Zitieren

APA

Goddard, W., & LaVey, D. (2024). Illuminating a Graph. Ars Combinatoria. https://doi.org/10.61091/ars-60-03

Vancouver

Goddard W, LaVey D. Illuminating a Graph. Ars Combinatoria. 2024. doi:10.61091/ars-60-03

BibTeX
@article{Goddard2024,
  author = {Goddard, Wayne and LaVey, Deirdre},
  title = {Illuminating a Graph},
  journal = {Ars Combinatoria},
  year = {2024},
  doi = {10.61091/ars-60-03}
}
Kostenlos starten →