Automorphism groups of graph covers and uniform subset graphs

Abstract

Hofmeister considered the automorphism groups of antipodal graphs through the exploration of graph covers. In this note we extend the exploration of automorphism groups of distance preserving graph covers. We apply the technique of graph covers to determine the automorphism groups of uniform subset graphs Γ ( 2 k , k , k − 1 ) and Γ ( 2 k , k , 1 ) . The determination of automorphism groups answers a conjecture posed by Mark Ramras and Elizabeth Donovan. They conjectured that Aut ( Γ ( 2 k , k , k − 1 ) ) ≅ S 2 k × , where T is the complementation map X ↦ T ( X ) = X c = { 1 , 2 , … , 2 k } ∖ X , and X is a k -subset of Ω = { 1 , 2 , … , 2 k } . Keywords: Graph covers, Antipodal graphs, Uniform subset graphs