(2021) The Largest Connected Subgraph Game.

Text
The_Largest_Connected_Subgraph_Game.pdf Download (1MB)  Preview 
Abstract
We introduce the largest connected subgraph game played on an undirected graph G. Each round, Alice colours an uncoloured vertex of G red, and then, Bob colours one blue. Once every vertex is coloured, Alice (Bob, resp.) wins if there is a red (blue, resp.) connected subgraph whose order is greater than that of any blue (red, resp.) connected subgraph. If neither player wins, it is a draw. We prove that Alice can ensure Bob never wins, and define a class of graphs (reflection graphs) in which the game is a draw. We show that the game is PSPACEcomplete in bipartite graphs of diameter 5, and that recognising reflection graphs is GIhard. We prove that the game is a draw in paths if and only if the path has even order or at least 11 vertices, and that Alice wins in cycles if and only if the cycle is of odd order. We also give an algorithm computing the outcome of the game in cographs in linear time.
Item Type:  Conference or Workshop Item (A Paper) (Paper) 

Divisions:  Dániel Marx (DM) 
Conference:  WG International Workshop on GraphTheoretic Concepts in Computer Science 
Depositing User:  Fionn Mc Inerney 
Date Deposited:  14 Dec 2021 11:01 
Last Modified:  14 Dec 2021 11:01 
Primary Research Area:  NRA2: Reliable Security Guarantees 
URI:  https://publications.cispa.saarland/id/eprint/3549 
Actions
Actions (login required)
View Item 