The Maximal Subgroups and the Complexity of the Flow Semigroup of Finite (Di)graphs

Gábor Horváth, Chrystopher Nehaniv, Károly Podoski

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)
98 Downloads (Pure)

Abstract

The flow semigroup, introduced by John Rhodes, is an invariant for digraphs and a complete invariant for graphs. We refine and prove Rhodes's conjecture on the structure of the maximal groups in the flow semigroup for finite, antisymmetric, strongly connected graphs. Building on this result, we investigate and fully describe the structure and actions of the maximal subgroups of the flow semigroup acting on all but k points for all finite digraphs and graphs for all k >=1. A linear algorithm is presented to determine these so-called 'defect k groups' for any finite (di)graph. Finally, we prove that the complexity of the flow semigroup of a 2-vertex connected (and strongly connected di)graph with n vertices is n- 2, completely confirming Rhodes's conjecture for such (di)graphs.
Original languageEnglish
Pages (from-to)863-886
Number of pages24
JournalInternational Journal of Algebra and Computation
Volume27
Issue number7
Early online date26 Sept 2017
DOIs
Publication statusPublished - 30 Nov 2017

Fingerprint

Dive into the research topics of 'The Maximal Subgroups and the Complexity of the Flow Semigroup of Finite (Di)graphs'. Together they form a unique fingerprint.

Cite this