Automorphism groups and adversarial vertex deletions
From MaRDI portal
Publication:2938239
zbMATH Open1305.05104arXiv1201.4367MaRDI QIDQ2938239FDOQ2938239
Authors: Derrick Stolee 
Publication date: 14 January 2015
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.
Full work available at URL: https://arxiv.org/abs/1201.4367
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
Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Finite automorphism groups of algebraic, geometric, or combinatorial structures (20B25)
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)
