Symmetry Dynamics of Graphs

Problem and Results Summary

**Question.** How do the automorphism groups of a graph change as vertices and edges are added or removed?

Here is a surprising fact.

**Theorem.** Given any two finite groups $\Gamma_1$ and $\Gamma_2$, there exists a graph $G$ and a vertex $v \in V(G)$ such that the automorphism group of $G$ is isomorphic to $\Gamma_1$ and the automorphism group of $G - v$ is isomorphic to $\Gamma_2$.

Further, this concept can be greatly generalized to all possible finite list of graphs and finite list of vertex deletions, even if the existential and universal quantifiers alternate (see "Automorphism Groups and Adversarial Vertex Deletions").

Research Papers

S. G. Hartke, H. Kolb, J. Nishikawa, D. Stolee,
"Automorphism groups of a graph and a vertex-deleted subgraph,"
*Electronic Journal of Combinatorics* **17**(1) R134.

Web Version ArXiv Version Official Version

Web Version ArXiv Version Official Version

D. Stolee, Automorphism Groups and Adversarial Vertex Deletions,
to appear in *Australasian Journal of Combinatorics*.

Web Version ArXiv Version

Web Version ArXiv Version

Presentations