CISPA
Browse
cispa_all_3780.pdf (597.77 kB)

On a vertex-capturing game

Download (597.77 kB)
journal contribution
posted on 2023-11-29, 18:06 authored by Julien Bensmail, Fionn McInerney
In this paper, we study the recently introduced scoring game played on graphs called the Edge-Balanced Index Game. This game is played on a graph by two players, Alice and Bob, who take turns colouring an uncoloured edge of the graph. Alice plays first and colours edges red, while Bob colours edges blue. The game ends once all the edges have been coloured. A player captures a vertex if more than half of its incident edges are coloured by that player, and the player that captures the most vertices wins. Using classical arguments from the field, we first prove general properties of this game. Namely, we prove that there is no graph in which Bob can win (if Alice plays optimally), while Alice can never capture more than 2 more vertices than Bob (if Bob plays optimally). Through dedicated arguments, we then investigate more specific properties of the game, and focus on its outcome when played in particular graph classes. Specifically, we determine the outcome of the game in paths, cycles, complete bipartite graphs, and Cartesian grids, and give partial results for trees and complete graphs.

History

Preferred Citation

Julien Bensmail and Fionn McInerney. On a vertex-capturing game. In: Theoretical Computer Science. 2022.

Primary Research Area

  • Algorithmic Foundations and Cryptography

Legacy Posted Date

2022-09-23

Journal

Theoretical Computer Science

Pages

27 - 46

Open Access Type

  • Green

Sub Type

  • Article

BibTeX

@article{cispa_all_3780, title = "On a vertex-capturing game", author = "Bensmail, Julien and McInerney, Fionn", journal="{Theoretical Computer Science}", year="2022", }

Usage metrics

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC