TY - JOUR
T1 - The Maximal Subgroups and the Complexity of the Flow Semigroup of Finite (Di)graphs
AU - Horváth, Gábor
AU - Nehaniv, Chrystopher
AU - Podoski, Károly
N1 - Preprint of an article first published online in International Journal of Algebra and Computation, September 2017, doi:
https://doi.org/10.1142/S0218196717500412.
© 2017 Copyright World Scientific Publishing Company.
http://www.worldscientific.com/worldscinet/ijac.
Accepted Manuscript version is under embargo. Embargo end date: 26 September 2018.
PY - 2017/11/30
Y1 - 2017/11/30
N2 - 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.
AB - 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.
UR - https://arxiv.org/abs/1705.09577
UR - http://www.worldscientific.com/doi/pdfplus/10.1142/S0218196717500412
U2 - 10.1142/S0218196717500412
DO - 10.1142/S0218196717500412
M3 - Article
SN - 0218-1967
VL - 27
SP - 863
EP - 886
JO - International Journal of Algebra and Computation
JF - International Journal of Algebra and Computation
IS - 7
ER -