Automorphism groups and adversarial vertex deletions
From MaRDI portal
Publication:2938239
Abstract: 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.
Recommendations
- Automorphism groups of a graph and a vertex-deleted subgraph
- Simple graphs containing induced subgraphs whose automorphism groups are isomorphic to subgroups of a given finite group
- Automorphism groups of graphs with forbidden subgraphs
- Simultaneous representations of groups
- scientific article; zbMATH DE number 3853103
This page was built for publication: Automorphism groups and adversarial vertex deletions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2938239)
