{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,3]],"date-time":"2022-04-03T19:09:08Z","timestamp":1649012948067},"reference-count":10,"publisher":"World Scientific Pub Co Pte Lt","issue":"03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2018,4]]},"abstract":"<jats:p> In interconnection network topologies, the [Formula: see text]-dimensional star graph [Formula: see text] has [Formula: see text] vertices corresponding to permutations [Formula: see text] of [Formula: see text] symbols [Formula: see text] and edges which exchange the positions of the first symbol [Formula: see text] with any one of the other symbols. The star graph compares favorably with the familiar [Formula: see text]-cube on degree, diameter and a number of other parameters. A desirable property which has not been fully evaluated in star graphs is the presence of multiple edge-disjoint Hamilton cycles which are important for fault-tolerance. The only known method for producing multiple edge-disjoint Hamilton cycles in [Formula: see text] has been to label the edges in a certain way and then take images of a known base 2-labelled Hamilton cycle under different automorphisms that map labels consistently. However, optimal bounds for producing edge-disjoint Hamilton cycles in this way, and whether Hamilton decompositions can be produced, are not known for any [Formula: see text] other than for the case of [Formula: see text] which does provide a Hamilton decomposition. In this paper we show that, for all n, not more than [Formula: see text], where [Formula: see text] is Euler\u2019s totient function, edge-disjoint Hamilton cycles can be produced by such automorphisms. Thus, for non-prime [Formula: see text], a Hamilton decomposition cannot be produced. We show that the [Formula: see text] upper bound can be achieved for all even [Formula: see text]. In particular, if [Formula: see text] is a power of 2, [Formula: see text] has a Hamilton decomposable spanning subgraph comprising more than half of the edges of [Formula: see text]. Our results produce a better than twofold improvement on the known bounds for any kind of edge-disjoint Hamilton cycles in [Formula: see text]-dimensional star graphs for general [Formula: see text]. <\/jats:p>","DOI":"10.1142\/s0129054118500090","type":"journal-article","created":{"date-parts":[[2018,5,8]],"date-time":"2018-05-08T00:13:37Z","timestamp":1525738417000},"page":"377-389","source":"Crossref","is-referenced-by-count":1,"title":["Optimal Bounds for Disjoint Hamilton Cycles in Star Graphs"],"prefix":"10.1142","volume":"29","author":[{"given":"Parisa","family":"Derakhshan","sequence":"first","affiliation":[{"name":"Department of Computer Science, Loughborough University, Loughborough LE11 3TU, United Kingdom"}]},{"given":"Walter","family":"Hussak","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Loughborough University, Loughborough LE11 3TU, United Kingdom"}]}],"member":"219","published-online":{"date-parts":[[2018,5,7]]},"reference":[{"key":"S0129054118500090BIB002","doi-asserted-by":"publisher","DOI":"10.1002\/jcd.10066"},{"key":"S0129054118500090BIB003","doi-asserted-by":"publisher","DOI":"10.1016\/S1383-7621(03)00020-1"},{"key":"S0129054118500090BIB004","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(95)00162-1"},{"key":"S0129054118500090BIB005","doi-asserted-by":"publisher","DOI":"10.1080\/00207160.2012.741226"},{"issue":"1","key":"S0129054118500090BIB006","first-page":"39","volume":"4","author":"Hussak W.","year":"2010","journal-title":"Int. J. Comput. Inf. Engin."},{"key":"S0129054118500090BIB007","first-page":"17","volume":"3","author":"Kompel\u2019makher V. L.","year":"1975","journal-title":"Kibernetika"},{"issue":"5","key":"S0129054118500090BIB008","first-page":"97","volume":"5","author":"Lafiti S.","year":"1994","journal-title":"IEEE Trans. Parallel and Distributed Syst."},{"key":"S0129054118500090BIB009","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2009.10.001"},{"key":"S0129054118500090BIB010","doi-asserted-by":"publisher","DOI":"10.1016\/j.sysarc.2004.05.003"},{"key":"S0129054118500090BIB011","first-page":"83","volume":"84","author":"Tripathy C. R.","year":"2004","journal-title":"J. Institute of Engineers (India)"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054118500090","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T15:26:46Z","timestamp":1565105206000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054118500090"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,4]]},"references-count":10,"journal-issue":{"issue":"03","published-online":{"date-parts":[[2018,5,7]]},"published-print":{"date-parts":[[2018,4]]}},"alternative-id":["10.1142\/S0129054118500090"],"URL":"https:\/\/doi.org\/10.1142\/s0129054118500090","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,4]]}}}