Show simple item record

dc.contributor.authorHorváth, Gábor
dc.contributor.authorNehaniv, Chrystopher
dc.contributor.authorPodoski, Károly
dc.date.accessioned2018-01-30T22:12:40Z
dc.date.available2018-01-30T22:12:40Z
dc.date.issued2017-11-30
dc.identifier.citationHorváth , G , Nehaniv , C & Podoski , K 2017 , ' The Maximal Subgroups and the Complexity of the Flow Semigroup of Finite (Di)graphs ' , International Journal of Algebra and Computation , vol. 27 , no. 7 , pp. 863-886 . https://doi.org/10.1142/S0218196717500412
dc.identifier.issn0218-1967
dc.identifier.urihttp://hdl.handle.net/2299/19641
dc.descriptionPreprint 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.
dc.description.abstractThe 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.en
dc.format.extent24
dc.format.extent797929
dc.format.extent702132
dc.language.isoeng
dc.relation.ispartofInternational Journal of Algebra and Computation
dc.titleThe Maximal Subgroups and the Complexity of the Flow Semigroup of Finite (Di)graphsen
dc.contributor.institutionSchool of Computer Science
dc.contributor.institutionCentre for Computer Science and Informatics Research
dc.contributor.institutionAdaptive Systems
dc.description.statusPeer reviewed
dc.date.embargoedUntil2018-09-26
dc.identifier.urlhttps://arxiv.org/abs/1705.09577
dc.identifier.urlhttp://www.worldscientific.com/doi/pdfplus/10.1142/S0218196717500412
rioxxterms.versionofrecord10.1142/S0218196717500412
rioxxterms.typeJournal Article/Review
herts.preservation.rarelyaccessedtrue


Files in this item

Thumbnail
Thumbnail

This item appears in the following Collection(s)

Show simple item record