Automorphism Groups and Adversarial Vertex Deletions

Original · EN

Any finite group can be encoded as the automorphism group of an unlabeled simple graph. Recently Hartke, Kolb, Nishikawa, and Stolee (2010) demonstrated a construction that allows any ordered pair of finite groups to be represented as the automorphism group of a graph and a vertex-deleted subgraph. In this note, we describe a generalized scenario as a game between a player and an adversary: An adversary provides a list of finite groups and a number of rounds. The player constructs a graph with automorphism group isomorphic to the first group. In the following rounds, the adversary selects a group and the player deletes a vertex such that the automorphism group of the corresponding vertex-deleted subgraph is isomorphic to the selected group. We provide a construction that allows the player to appropriately respond to any sequence of challenges from the adversary.