{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:12:31Z","timestamp":1760202751979},"reference-count":14,"publisher":"World Scientific Pub Co Pte Lt","issue":"07","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Algebra Comput."],"published-print":{"date-parts":[[2017,11]]},"abstract":"<jats:p> The flow semigroup, introduced by Rhodes, is an invariant for digraphs and a complete invariant for graphs. After collecting previous partial results together, we refine and prove Rhodes\u2019s conjecture on the structure of the maximal groups in the flow semigroup for finite, antisymmetric, strongly connected digraphs. 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 [Formula: see text] points for all finite digraphs and graphs for all [Formula: see text]. A linear algorithm (in the number of edges) is presented to determine these so-called \u201cdefect [Formula: see text] groups\u201d 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 [Formula: see text] vertices is [Formula: see text], completely confirming Rhodes\u2019s conjecture for such (di)graphs. <\/jats:p>","DOI":"10.1142\/s0218196717500412","type":"journal-article","created":{"date-parts":[[2017,9,4]],"date-time":"2017-09-04T21:25:04Z","timestamp":1504560304000},"page":"863-886","source":"Crossref","is-referenced-by-count":2,"title":["The maximal subgroups and the complexity of the flow semigroup of finite (di)graphs"],"prefix":"10.1142","volume":"27","author":[{"given":"G\u00e1bor","family":"Horv\u00e1th","sequence":"first","affiliation":[{"name":"Institute of Mathematics, University of Debrecen, Pf. 400, Debrecen, 4002, Hungary"}]},{"given":"Chrystopher L.","family":"Nehaniv","sequence":"additional","affiliation":[{"name":"Royal Society Wolfson Biocomputation Research Laboratory, Centre for Computer Science and Informatics Research, University of Hertfordshire, College Lane, Hatfield, Hertfordshire AL10 9AB, UK"}]},{"given":"K\u00e1roly","family":"Podoski","sequence":"additional","affiliation":[{"name":"Alfr\u00e9d R\u00e9nyi Institute of Mathematics, 13\u201315 Re\u00e1ltanoda utca, Budapest, 1053, Hungary"}]}],"member":"219","published-online":{"date-parts":[[2017,11,28]]},"reference":[{"key":"S0218196717500412BIB001","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511623677"},{"key":"S0218196717500412BIB002","doi-asserted-by":"publisher","DOI":"10.1090\/surv\/007.1"},{"key":"S0218196717500412BIB003","doi-asserted-by":"publisher","DOI":"10.1090\/surv\/007.2"},{"key":"S0218196717500412BIB004","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14279-6"},{"key":"S0218196717500412BIB005","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0731-3"},{"key":"S0218196717500412BIB007","volume-title":"Handbook of Combinatorics","volume":"1","author":"Graham R. L.","year":"1995"},{"key":"S0218196717500412BIB008","doi-asserted-by":"publisher","DOI":"10.1145\/362248.362272"},{"key":"S0218196717500412BIB009","volume-title":"Applications of Automata Theory and Algebra: Via the Mathematical Theory of Complexity to Biology, Physics, Psychology, Philosophy, and Games","author":"Rhodes J.","year":"2010"},{"key":"S0218196717500412BIB010","doi-asserted-by":"publisher","DOI":"10.1016\/0022-4049(71)90012-0"},{"key":"S0218196717500412BIB011","doi-asserted-by":"publisher","DOI":"10.2307\/2303897"},{"key":"S0218196717500412BIB012","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-8594-1"},{"key":"S0218196717500412BIB013","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(74)90003-9"},{"key":"S0218196717500412BIB014","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1932-1501641-2"},{"key":"S0218196717500412BIB015","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(74)90098-7"}],"container-title":["International Journal of Algebra and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218196717500412","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T01:09:20Z","timestamp":1565140160000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218196717500412"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,11]]},"references-count":14,"journal-issue":{"issue":"07","published-online":{"date-parts":[[2017,11,28]]},"published-print":{"date-parts":[[2017,11]]}},"alternative-id":["10.1142\/S0218196717500412"],"URL":"https:\/\/doi.org\/10.1142\/s0218196717500412","relation":{},"ISSN":["0218-1967","1793-6500"],"issn-type":[{"value":"0218-1967","type":"print"},{"value":"1793-6500","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,11]]}}}