A Note on Counting Flows in Signed Graphs
| Autor: | Robert Šámal, Edita Rollová, Matt DeVos |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Polynomial (hyperelastic model)
Finite group 05C21 05C22 Fundamental theorem Astrophysics::High Energy Astrophysical Phenomena Applied Mathematics Order (ring theory) Graph Theoretical Computer Science Combinatorics Computational Theory and Mathematics Integer FOS: Mathematics Mathematics - Combinatorics Discrete Mathematics and Combinatorics Combinatorics (math.CO) Geometry and Topology Abelian group Signed graph Mathematics |
| Zdroj: | The Electronic Journal of Combinatorics. 26 |
| ISSN: | 1077-8926 |
| DOI: | 10.37236/7958 |
| Popis: | Tutte initiated the study of nowhere-zero flows and proved the following fundamental theorem: For every graph $G$ there is a polynomial $f$ so that for every abelian group $\Gamma$ of order $n$, the number of nowhere-zero $\Gamma$-flows in $G$ is $f(n)$. For signed graphs (which have bidirected orientations), the situation is more subtle. For a finite group $\Gamma$, let $\epsilon_2(\Gamma)$ be the largest integer $d$ so that $\Gamma$ has a subgroup isomorphic to $\mathbb{Z}_2^d$. We prove that for every signed graph $G$ and $d \ge 0$ there is a polynomial $f_d$ so that $f_d(n)$ is the number of nowhere-zero $\Gamma$-flows in $G$ for every abelian group $\Gamma$ with $\epsilon_2(\Gamma) = d$ and $|\Gamma| = 2^d n$. Beck and Zaslavsky had previously established the special case of this result when $d=0$ (i.e., when $\Gamma$ has odd order). Comment: 7 pages |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|