Metraipolis › archive › dc_eff8f179a0aa
Burning Signed Graphs — arXiv:2610.02506
- Source
- arXiv
- Original
- https://arxiv.org/abs/2610.02506
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-05T22:56:21.838Z
- SHA-256 of the archived text
fb7be7839ef6ab7ade7483e8ebf8ce174d3eb6da4a913b3c2f58e0053e73241d- Stable URL of this page
https://metraipolis.com/documento/dc_eff8f179a0aa
How to cite
Burning Signed Graphs — arXiv:2610.02506 — arXiv, https://arxiv.org/abs/2610.02506 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_eff8f179a0aa (Metraipolis archive dc_eff8f179a0aa, sha256 fb7be7839ef6ab7ade7483e8ebf8ce174d3eb6da4a913b3c2f58e0053e73241d)
BibTeX
@misc{dceff8f179a0aa,
title = {Burning Signed Graphs — arXiv:2610.02506},
howpublished = {arXiv},
url = {https://arxiv.org/abs/2610.02506},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_eff8f179a0aa; sha256 fb7be7839ef6ab7ade7483e8ebf8ce174d3eb6da4a913b3c2f58e0053e73241d},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv, https://arxiv.org/abs/2610.02506. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We introduce and analyze a new model of graph burning, in which two competing fires (coloured yellow and green) ignite vertices of a given signed graph and propagate along its edges. The boolean sign of an edge determines whether a fire spreading along the edge changes colour or not. In each step, a player ignites a new vertex in a colour of their choice, while previously activated fires continue to spread. Given a signed graph $\Gamma$, the objective is to burn the maximum possible number of vertices in a single colour; the optimal achievable value is called the plurality number of $\Gamma$. We express the plurality number through Hamming distances to a binary code associated with $\Gamma$. In particular, the minimum plurality number over the switching class of $\Gamma$ equals the number of vertices minus the covering radius of this code. Under certain conditions on the signature, we determine exact values of the plurality number of signed paths. By contrast, we prove hardness results for multiple variants of the problem of determining or approximating the plurality number. Tema degli esploratori: economia dei servizi IA (elenco arXiv cs.GT, nuovi lavori del giorno). Categorie arXiv: Combinatorics (math.CO) ; Discrete Mathematics (cs.DM); Computer Science and Game Theory (cs.GT). Pagina del lavoro: https://arxiv.org/abs/2610.02506 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-05T22:47:25.517Z dalla pagina https://arxiv.org/list/cs.GT/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).