***************************************************************************** * www.FindStat.org - The Combinatorial Statistic Finder * * * * Copyright (C) 2019 The FindStatCrew * * * * This information is distributed in the hope that it will be useful, * * but WITHOUT ANY WARRANTY; without even the implied warranty of * * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. * ***************************************************************************** ----------------------------------------------------------------------------- Statistic identifier: St001783 ----------------------------------------------------------------------------- Collection: Graphs ----------------------------------------------------------------------------- Description: The number of odd automorphisms of a graph. Let $D$ be an arbitrary orientation of a graph $G$. Then an automorphism of $G$ is odd, if it reverses the orientation of an odd number of edges of $D$. The graphs on $n$ vertices without any odd automorphisms are equinumerous with the number of non-isomorphic $n$-team tournaments, see [2]. The odd automorphisms of the complete graphs are precisely the even permutations. ----------------------------------------------------------------------------- References: [1] Number of outcomes of unlabeled n-team round-robin tournaments. [[OEIS:A000568]] [2] Royle, G. F., Praeger, C. E., Glasby, S. P., Freedman, S. D., Devillers, A. Tournaments and Even Graphs are Equinumerous [[arXiv:2204.01947]] ----------------------------------------------------------------------------- Code: def is_odd_automorphism(D, g): count = 0 for a, b in D.edges(labels=False): c, d = g(a), g(b) if D.has_edge(c, d) and not D.has_edge(d, c): pass elif D.has_edge(d, c) and not D.has_edge(c, d): count += 1 else: raise ValueError("%s is mapped to %s" % ((a,b), (c,d))) return is_odd(count) def statistic(G): D = next(G.orientations()) count = 0 for g in G.automorphism_group(): if is_odd_automorphism(D, g): count += 1 return count ----------------------------------------------------------------------------- Statistic values: ([],1) => 0 ([],2) => 0 ([(0,1)],2) => 1 ([],3) => 0 ([(1,2)],3) => 1 ([(0,2),(1,2)],3) => 0 ([(0,1),(0,2),(1,2)],3) => 3 ([],4) => 0 ([(2,3)],4) => 2 ([(1,3),(2,3)],4) => 0 ([(0,3),(1,3),(2,3)],4) => 0 ([(0,3),(1,2)],4) => 4 ([(0,3),(1,2),(2,3)],4) => 1 ([(1,2),(1,3),(2,3)],4) => 3 ([(0,3),(1,2),(1,3),(2,3)],4) => 1 ([(0,2),(0,3),(1,2),(1,3)],4) => 0 ([(0,2),(0,3),(1,2),(1,3),(2,3)],4) => 2 ([(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)],4) => 12 ([],5) => 0 ([(3,4)],5) => 6 ([(2,4),(3,4)],5) => 0 ([(1,4),(2,4),(3,4)],5) => 0 ([(0,4),(1,4),(2,4),(3,4)],5) => 0 ([(1,4),(2,3)],5) => 4 ([(1,4),(2,3),(3,4)],5) => 1 ([(0,1),(2,4),(3,4)],5) => 2 ([(2,3),(2,4),(3,4)],5) => 6 ([(0,4),(1,4),(2,3),(3,4)],5) => 0 ([(1,4),(2,3),(2,4),(3,4)],5) => 1 ([(0,4),(1,4),(2,3),(2,4),(3,4)],5) => 2 ([(1,3),(1,4),(2,3),(2,4)],5) => 0 ([(0,4),(1,2),(1,3),(2,4),(3,4)],5) => 0 ([(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 2 ([(0,4),(1,3),(2,3),(2,4),(3,4)],5) => 1 ([(0,4),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 0 ([(0,3),(0,4),(1,3),(1,4),(2,3),(2,4)],5) => 0 ([(0,3),(0,4),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 6 ([(0,4),(1,3),(2,3),(2,4)],5) => 0 ([(0,1),(2,3),(2,4),(3,4)],5) => 6 ([(0,3),(1,2),(1,4),(2,4),(3,4)],5) => 1 ([(0,3),(0,4),(1,2),(1,4),(2,4),(3,4)],5) => 4 ([(0,3),(0,4),(1,2),(1,4),(2,3)],5) => 5 ([(0,1),(0,4),(1,3),(2,3),(2,4),(3,4)],5) => 0 ([(0,3),(0,4),(1,2),(1,4),(2,3),(2,4),(3,4)],5) => 1 ([(0,4),(1,2),(1,3),(2,3),(2,4),(3,4)],5) => 1 ([(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 12 ([(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 3 ([(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 2 ([(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4)],5) => 2 ([(0,2),(0,3),(0,4),(1,2),(1,3),(1,4),(2,4),(3,4)],5) => 0 ([(0,2),(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 6 ([(0,1),(0,2),(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 60 ([],6) => 0 ([(4,5)],6) => 24 ([(3,5),(4,5)],6) => 0 ([(2,5),(3,5),(4,5)],6) => 0 ([(1,5),(2,5),(3,5),(4,5)],6) => 0 ([(0,5),(1,5),(2,5),(3,5),(4,5)],6) => 0 ([(2,5),(3,4)],6) => 8 ([(2,5),(3,4),(4,5)],6) => 2 ([(1,2),(3,5),(4,5)],6) => 2 ([(3,4),(3,5),(4,5)],6) => 18 ([(1,5),(2,5),(3,4),(4,5)],6) => 0 ([(0,1),(2,5),(3,5),(4,5)],6) => 6 ([(2,5),(3,4),(3,5),(4,5)],6) => 2 ([(0,5),(1,5),(2,5),(3,4),(4,5)],6) => 0 ([(1,5),(2,5),(3,4),(3,5),(4,5)],6) => 2 ([(0,5),(1,5),(2,5),(3,4),(3,5),(4,5)],6) => 6 ([(2,4),(2,5),(3,4),(3,5)],6) => 0 ([(0,5),(1,5),(2,4),(3,4)],6) => 0 ([(1,5),(2,3),(2,4),(3,5),(4,5)],6) => 0 ([(0,5),(1,5),(2,3),(3,4),(4,5)],6) => 0 ([(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 4 ([(1,5),(2,4),(3,4),(3,5),(4,5)],6) => 1 ([(0,5),(1,5),(2,4),(3,4),(4,5)],6) => 4 ([(0,5),(1,5),(2,3),(2,4),(3,5),(4,5)],6) => 0 ([(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 0 ([(0,5),(1,5),(2,4),(3,4),(3,5),(4,5)],6) => 0 ([(0,5),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 0 ([(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)],6) => 0 ([(0,5),(1,4),(2,4),(2,5),(3,4),(3,5)],6) => 0 ([(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)],6) => 0 ([(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 6 ([(0,5),(1,4),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 2 ([(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 0 ([(0,4),(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)],6) => 0 ([(0,4),(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 24 ([(0,5),(1,4),(2,3)],6) => 24 ([(1,5),(2,4),(3,4),(3,5)],6) => 0 ([(0,1),(2,5),(3,4),(4,5)],6) => 2 ([(1,2),(3,4),(3,5),(4,5)],6) => 6 ([(0,5),(1,4),(2,3),(3,5),(4,5)],6) => 0 ([(1,4),(2,3),(2,5),(3,5),(4,5)],6) => 1 ([(0,1),(2,5),(3,4),(3,5),(4,5)],6) => 2 ([(0,4),(1,5),(2,3),(2,5),(3,5),(4,5)],6) => 1 ([(1,4),(1,5),(2,3),(2,5),(3,5),(4,5)],6) => 4 ([(0,5),(1,4),(1,5),(2,3),(2,5),(3,5),(4,5)],6) => 4 ([(1,4),(1,5),(2,3),(2,5),(3,4)],6) => 5 ([(0,5),(1,4),(2,3),(2,4),(3,5),(4,5)],6) => 0 ([(1,2),(1,5),(2,4),(3,4),(3,5),(4,5)],6) => 0 ([(0,5),(1,2),(1,4),(2,3),(3,5),(4,5)],6) => 1 ([(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6) => 1 ([(0,5),(1,4),(2,3),(3,4),(3,5),(4,5)],6) => 3 ([(0,5),(1,2),(1,5),(2,4),(3,4),(3,5),(4,5)],6) => 0 ([(0,5),(1,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 0 ([(1,4),(1,5),(2,3),(2,5),(3,4),(3,5),(4,5)],6) => 1 ([(0,5),(1,4),(1,5),(2,3),(2,5),(3,4),(3,5),(4,5)],6) => 1 ([(0,5),(1,4),(2,3),(2,4),(3,5)],6) => 1 ([(0,1),(2,4),(2,5),(3,4),(3,5)],6) => 8 ([(0,5),(1,5),(2,3),(2,4),(3,4)],6) => 6 ([(0,4),(1,2),(1,3),(2,5),(3,5),(4,5)],6) => 0 ([(0,4),(1,2),(1,5),(2,5),(3,4),(3,5)],6) => 1 ([(0,4),(1,2),(2,5),(3,4),(3,5),(4,5)],6) => 0 ([(0,1),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 4 ([(0,4),(1,4),(2,3),(2,5),(3,5),(4,5)],6) => 2 ([(0,3),(0,4),(1,2),(1,5),(2,5),(3,5),(4,5)],6) => 2 ([(0,3),(1,4),(1,5),(2,4),(2,5),(3,5),(4,5)],6) => 0 ([(0,4),(1,2),(1,5),(2,5),(3,4),(3,5),(4,5)],6) => 1 ([(0,1),(0,5),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 2 ([(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 24 ([(0,5),(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6) => 2 ([(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 3 ([(0,5),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 6 ([(0,1),(0,5),(1,4),(2,4),(2,5),(3,4),(3,5)],6) => 2 ([(0,3),(0,5),(1,3),(1,5),(2,4),(2,5),(3,4),(4,5)],6) => 0 ([(0,3),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 2 ([(0,5),(1,4),(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6) => 0 ([(0,1),(0,5),(1,4),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 0 ([(0,4),(0,5),(1,4),(1,5),(2,3),(2,5),(3,4),(3,5),(4,5)],6) => 0 ([(0,5),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5)],6) => 1 ([(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 2 ([(0,5),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 2 ([(0,5),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 1 ([(0,4),(0,5),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5)],6) => 4 ([(0,4),(0,5),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 4 ([(0,5),(1,3),(1,4),(2,3),(2,4),(3,5),(4,5)],6) => 0 ([(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5)],6) => 2 ([(0,5),(1,3),(1,4),(2,3),(2,4),(2,5),(3,5),(4,5)],6) => 0 ([(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,5),(4,5)],6) => 0 ([(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,5),(4,5)],6) => 0 ([(0,4),(0,5),(1,2),(1,3),(2,5),(3,4)],6) => 0 ([(0,3),(0,5),(1,2),(1,5),(2,4),(3,4),(4,5)],6) => 2 ([(0,5),(1,2),(1,4),(2,3),(3,4),(3,5),(4,5)],6) => 0 ([(0,1),(0,2),(1,5),(2,4),(3,4),(3,5),(4,5)],6) => 1 ([(0,5),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5)],6) => 2 ([(0,5),(1,3),(1,4),(2,4),(2,5),(3,4),(3,5)],6) => 0 ([(0,1),(0,5),(1,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 0 ([(0,4),(1,3),(1,5),(2,3),(2,4),(2,5),(3,5),(4,5)],6) => 0 ([(0,4),(0,5),(1,3),(1,5),(2,3),(2,4),(3,5),(4,5)],6) => 0 ([(0,4),(0,5),(1,3),(1,5),(2,3),(2,4),(2,5),(3,5),(4,5)],6) => 0 ([(0,4),(0,5),(1,2),(1,3),(2,4),(2,5),(3,4),(3,5)],6) => 0 ([(0,5),(1,2),(1,3),(1,4),(2,3),(2,4),(3,5),(4,5)],6) => 2 ([(0,4),(0,5),(1,2),(1,3),(1,5),(2,4),(2,5),(3,4),(3,5)],6) => 0 ([(0,4),(0,5),(1,2),(1,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 2 ([(0,4),(0,5),(1,2),(1,3),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 0 ([(0,5),(1,2),(1,3),(1,4),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 0 ([(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 6 ([(0,5),(1,3),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 1 ([(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 2 ([(0,4),(0,5),(1,2),(1,4),(2,3),(2,5),(3,4),(3,5),(4,5)],6) => 0 ([(0,4),(0,5),(1,3),(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6) => 3 ([(0,4),(0,5),(1,3),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 1 ([(0,4),(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 2 ([(0,3),(0,4),(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5)],6) => 36 ([(0,1),(0,2),(0,3),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 6 ([(0,4),(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5)],6) => 0 ([(0,3),(0,4),(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,5),(4,5)],6) => 0 ([(0,3),(0,4),(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 18 ([(0,4),(0,5),(1,2),(1,3),(2,3),(4,5)],6) => 36 ([(0,2),(1,4),(1,5),(2,3),(3,4),(3,5),(4,5)],6) => 1 ([(0,1),(0,5),(1,5),(2,3),(2,4),(3,4),(4,5)],6) => 4 ([(0,1),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 24 ([(0,1),(0,5),(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6) => 2 ([(0,1),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 3 ([(0,1),(0,5),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 6 ([(0,4),(0,5),(1,2),(1,3),(2,3),(2,5),(3,4),(4,5)],6) => 0 ([(0,4),(0,5),(1,2),(1,3),(1,4),(2,3),(2,5),(3,5),(4,5)],6) => 1 ([(0,3),(1,2),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 2 ([(0,3),(0,5),(1,2),(1,4),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 1 ([(0,1),(0,5),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 2 ([(0,3),(0,5),(1,2),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 1 ([(0,3),(0,4),(0,5),(1,2),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)],6) => 8 ([(0,3),(0,4),(0,5),(1,2),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 8 ([(0,4),(0,5),(1,3),(1,5),(2,3),(2,4),(2,5),(3,4)],6) => 1 ([(0,1),(0,5),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5)],6) => 2 ([(0,3),(0,4),(1,2),(1,4),(1,5),(2,3),(2,5),(3,5),(4,5)],6) => 1 ([(0,3),(0,4),(0,5),(1,2),(1,4),(1,5),(2,3),(2,5),(3,5),(4,5)],6) => 5 ([(0,3),(0,4),(0,5),(1,2),(1,4),(1,5),(2,3),(2,5),(3,4)],6) => 6 ([(0,1),(0,3),(0,5),(1,2),(1,4),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 0 ([(0,4),(0,5),(1,2),(1,3),(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6) => 0 ([(0,1),(0,4),(0,5),(1,3),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 0 ([(0,3),(0,4),(0,5),(1,2),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 2 ([(0,2),(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6) => 1 ([(0,4),(0,5),(1,2),(1,3),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 4 ([(0,4),(0,5),(1,2),(1,3),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 1 ([(0,5),(1,2),(1,3),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 3 ([(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 60 ([(0,5),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 12 ([(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 6 ([(0,3),(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 6 ([(0,3),(0,4),(0,5),(1,2),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5)],6) => 2 ([(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5)],6) => 6 ([(0,1),(0,4),(0,5),(1,2),(1,3),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 4 ([(0,3),(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,5),(4,5)],6) => 2 ([(0,2),(0,3),(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)],6) => 0 ([(0,2),(0,3),(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 8 ([(0,2),(0,3),(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 24 ([(0,1),(0,2),(0,3),(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 360 ----------------------------------------------------------------------------- Created: Apr 06, 2022 at 10:26 by Martin Rubey ----------------------------------------------------------------------------- Last Updated: Apr 27, 2022 at 10:37 by Martin Rubey