Symmetry Dynamics with Graph Modifications (2010)

Originators: Stephen G. Hartke, Hannah Kolb, Jared Nishikawa, Derrick Stolee (presented by Derrick Stolee - REGS 2011)

Definitions: For a graph G, we denote the automorphism group of G by Aut(G).

Background: In studying reconstruction problems, automorphisms of substructures lead to ambiguity when constructing the original structure. For instance, in the (Vertex) Reconstruction Conjecture, a list of unlabeled vertex-deleted subgraphs G-v₁,…,G-v_n is given, and the conjecture is that G can be determined (when n≥3.

The Reconstruction Problem suggested asking what information about the automorphism group (as an abstract group) of a graph is given by the automorphism group of a single vertex-deleted subgraph? The answer, perhaps surprisingly, is "nothing". This is due to the following theorem:

Theorem([HKNS10]): For any two finite groups Γ₁ and Γ₂, there is a graph G and a vertex v in V(G) such that Aut(G) is isomorphic to Γ₁ and Aut(G-v) is isomorphic to Γ₂.

An analogous theorem holds for edge-deletion. The proof of the vertex theorem constructs graphs whose number of vertices is cubic in the sizes of Γ₁ and Γ₂. Also, the resulting graph is very far from planar.

Question 1: For various classes of graphs, which pairs of groups occur as the automorphism group of a graph in the class and as the automorphism group of another graph in the class obtained by deleting a vertex or edge from the first graph?

Question 1a: For trees, which pairs of groups occur as the automorphism group of a tree T and:

1. A vertex-deleted subgraph? (This potentially results in a forest)
2. A leaf-deleted subtree?

Question 1b: For planar graphs, which pairs of groups occur?

Question 2: What if we delete multiple vertices? That is, for which sequences of k+1 finite groups Γ₀,Γ₁,&hellip,Γ_k does there exist a graph G containing vertices v₁,…,v_k such that Aut(G)≅Γ₀ and for all j between 1 and k:

• (Variant 1) Aut(G-v_j)≅Γ_j?
• (Variant 2) Aut(G-v₁-v₂-⋅⋅⋅-v_j)≅Γ_j?

Comments: The multi-group variant is likely true for all sequences of groups by generalizing the construction for pairs of groups.

References:
[HKNS10] 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), R-134, October 2010.