Ratio of Symmetries Between any two n-Node Graphs

Justus Isaiah Hibshman

paper

Ratio of Symmetries Between any two n-Node Graphs

arXiv:2205.05726

Abstract

Given any two graphs on the same vertex set, $G_{1} = (V, E_{1})$ and $G_{2} = (V, E_{2})$ , along with the difference between the two graphs $Δ = (E_{1} ∖ E_{2}) \cup (E_{2} ∖ E_{1})$ , we prove that the ratio of the sizes of the two graphs' automorphism groups is equivalent to the ratio of the sizes of $Δ$ 's automorphism orbits in $G_{1}$ and $G_{2}$ respectively. This result provides a link between graphs' symmetries that might otherwise seem to be unrelated.