Tournaments and Even Graphs are Equinumerous
| Autor: | Stephen Glasby, Saul Freedman, Alice Devillers, Cheryl Praeger, Gordon Royle |
|---|---|
| Přispěvatelé: | University of St Andrews. Pure Mathematics |
| Jazyk: | angličtina |
| Rok vydání: | 2022 |
| Předmět: |
Algebra and Number Theory
Cauchy-Frobenius theorem Tournaments Graph automorphisms G.2.1 G.2.2 Graph counting Graph isomorphisms MCP FOS: Mathematics T-DAS Discrete Mathematics and Combinatorics Mathematics - Combinatorics Combinatorics (math.CO) Graph enumeration 05C30 (Primary) 05C75 05A15 (secondary) |
| Popis: | A graph is called odd if there is an orientation of its edges and an automorphism that reverses the sense of an odd number of its edges, and even otherwise. Pontus von Br\"omssen (n\'e Andersson) showed that the existence of such an automorphism is independent of the orientation, and considered the question of counting pairwise non-isomorphic even graphs. Based on computational evidence, he made the rather surprising conjecture that the number of pairwise non-isomorphic even graphs on $n$ vertices is equal to the number of pairwise non-isomorphic tournaments on $n$ vertices. We prove this conjecture using a counting argument with several applications of the Cauchy-Frobenius Theorem. Comment: 9 pages. Corrected minor non-mathematical typos and slightly expanded the introduction |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|