Description
My talk is based on a joint work with G. Horváth and C. L. Nehaniv. The flow semigroup, introduced by Rhodes, is an invariant for digraphs and a complete
invariant for graphs. In this talk, after collecting previous partial results together, I will discuss our new approach and proof of Rhodes's conjecture on the structure of the maximal groups in the flow semigroup for finite, antisymmetric, strongly connected digraphs. Building on this result, we have a fully description of 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. In addition, a linear algorithm (in the number of edges) is presented to determine these so-called "defect k groups" for any finite (di)graph. Finally, it turns out that the complexity of the low 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.