Enumerating Switching Isomorphism Classes of Signed Graphs

Let Γ be a simple connected graph, and let {+,−}^E(Γ) be the set of signatures of Γ. For σ a signature of Γ, we call the pair Σ = (Γ,σ) a signed graph of Γ. We may define switching functions ζ_X ∈ {+, −}^V (Γ) that negate the sign of every edge {u, v} incident with exactly one vertex in the fiber X = ζ^{−1}(−). The group Sw(Γ) of switching functions acts X on the set of signed graphs of Γ and induces an equivalence relation of switching classes in its orbits; there are 2^{|E(Γ)|−|V (Γ)|+1} such classes. More interestingly, we may define a group SwAut(Γ) = Sw(Γ) ⋊ Aut(Γ) whose action on signed graphs combines both switching functions and graph automorphisms. We may also define switching automorphism groups SwAut(Σ) as subgroups of SwAut(Γ) that preserve individual signed graphs. The orbits of SwAut(Γ) on signed graphs represent the equivalence classes of signed graphs that are equivalent under some combination of switching and permuting vertices. We call these classes switching isomorphism classes, and their enumeration for an arbitrary graph is nontrivial. Following observations of Zaslavsky, we offer algorithms for the enumeration of switching isomorphism classes, and thus provide a means for counting such classes for arbitrary graphs. We also calculate a formula for the number of switching isomorphism classes of certain species of Generalized Petersen graphs, and provide data for the number of these classes for other graphs for which no formula is yet known. Finally, we include the abstract switching automorphism groups of all switching isomorphism classes for select graphs, as determined by our program