{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,10]],"date-time":"2024-07-10T19:46:07Z","timestamp":1720640767962},"reference-count":59,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2002,7,1]],"date-time":"2002-07-01T00:00:00Z","timestamp":1025481600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Electronic Notes in Discrete Mathematics"],"published-print":{"date-parts":[[2002,7]]},"DOI":"10.1016\/s1571-0653(04)00062-9","type":"journal-article","created":{"date-parts":[[2004,10,15]],"date-time":"2004-10-15T15:21:27Z","timestamp":1097853687000},"page":"140-156","source":"Crossref","is-referenced-by-count":0,"special_numbering":"C","title":["Basic Structures of Some Interconnection Networks"],"prefix":"10.1016","volume":"11","author":[{"given":"Eddie","family":"Cheng","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marc J.","family":"Lipman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S1571-0653(04)00062-9_NEWBIB1","unstructured":"S.B. Akers, D. Harel, and B. Kirshnamurthy. The star graph: An attractive alternative to the n-cube. Proc. Int'I Conf. Parallel Processing, pages 393\u2013400, 1987."},{"key":"10.1016\/S1571-0653(04)00062-9_NEWBIB2","doi-asserted-by":"crossref","first-page":"587","DOI":"10.1109\/TC.1981.1675844","article-title":"Fault diagnosis in boolean n-cube array of microprocessors","volume":"30","author":"Armstrong","year":"1981","journal-title":"IEEE Trans. Comput"},{"key":"10.1016\/S1571-0653(04)00062-9_NEWBIB3","first-page":"39","article-title":"A characterization of vertex-transitive graphs of toughness one","volume":"10","author":"Bagga","year":"1994","journal-title":"Bulletin of Inst. Comb. and its Apps"},{"key":"10.1016\/S1571-0653(04)00062-9_NEWBIB4","first-page":"141","article-title":"On the edge-integrity of graphs","volume":"60","author":"Bagga","year":"1987","journal-title":"Congr. Numer"},{"key":"10.1016\/S1571-0653(04)00062-9_NEWBIB5","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/0012-365X(94)90084-1","article-title":"Edge-integrity: A survey","volume":"124","author":"Bagga","year":"1994","journal-title":"Discrete Math"},{"issue":"5","key":"10.1016\/S1571-0653(04)00062-9_NEWBIB6","doi-asserted-by":"crossref","first-page":"531","DOI":"10.1109\/71.382321","article-title":"A well-behaved enumeration of star graphs","volume":"6","author":"Bagherzadeh","year":"1995","journal-title":"IEEE Trans. on Parallel and Dist. Sys"},{"key":"10.1016\/S1571-0653(04)00062-9_NEWBIB7","doi-asserted-by":"crossref","first-page":"17","DOI":"10.7155\/jgaa.00005","article-title":"A broadcasting algorithm with time and message optimum on arrangement graphs","volume":"2","author":"Bai","year":"1998","journal-title":"J. Graph Algorithms Appl"},{"key":"10.1016\/S1571-0653(04)00062-9_NEWBIB8","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1016\/0167-6377(92)90045-5","article-title":"Separating from the dominant of the spanning tree polytope","volume":"12","author":"Barahona","year":"1992","journal-title":"Oper. Research Lett"},{"key":"10.1016\/S1571-0653(04)00062-9_NEWBIB9","first-page":"103","article-title":"Integrity of trees and powers of cycles","volume":"58","author":"Barefoot","year":"1987","journal-title":"Congr. Numer"},{"key":"10.1016\/S1571-0653(04)00062-9_NEWBIB10","series-title":"The theory and application of graphs","first-page":"89","article-title":"Connectivity extremal problems and the design of reliable probabilistic networks","author":"Bauer","year":"1981"},{"key":"10.1016\/S1571-0653(04)00062-9_NEWBIB11","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1016\/0166-218X(90)90001-S","article-title":"Schmeichel Recognizing tough graphs is np-hard","volume":"28","author":"Bauer","year":"1990","journal-title":"Discrete Appl. Math"},{"issue":"4","key":"10.1016\/S1571-0653(04)00062-9_NEWBIB12","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1109\/TC.1984.1676437","article-title":"Generalized hypercube and hyperbus structures for a computer network","volume":"33","author":"Bhuyan","year":"1984","journal-title":"IEEE Trans. Comput"},{"key":"10.1016\/S1571-0653(04)00062-9_NEWBIB13","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1016\/0166-218X(92)90002-R","article-title":"Fractional arboricity, strength, and principal partitions in graphs and matroids","volume":"40","author":"Catlin","year":"1992","journal-title":"Discrete Appl. Math"},{"issue":"7","key":"10.1016\/S1571-0653(04)00062-9_NEWBIB14","doi-asserted-by":"crossref","first-page":"717","DOI":"10.1109\/71.508251","article-title":"Balanced spanning trees in complete and incomplete star graphs","volume":"7","author":"Chen","year":"1996","journal-title":"IEEE Trans. on Parallel and Dist. Sys"},{"key":"10.1016\/S1571-0653(04)00062-9_NEWBIB15","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/0020-0190(94)90013-2","article-title":"A faster algorithm for computing the strength of a network","volume":"49","author":"Cheng","year":"1994","journal-title":"Inform. Proc. Lett"},{"key":"10.1016\/S1571-0653(04)00062-9_NEWBIB16","unstructured":"E. Cheng and M.J. Lipman. Increasing the connectivity of split-stars. Congr. Numer. (to appear)."},{"key":"10.1016\/S1571-0653(04)00062-9_NEWBIB17","unstructured":"E. Cheng and M.J. Lipman. Vulnerability issues of star graphs and split-stars: strength and toughness, (submitted)."},{"key":"10.1016\/S1571-0653(04)00062-9_NEWBIB18","first-page":"47","article-title":"Disjoint paths in split-stars","volume":"137","author":"Cheng","year":"1999","journal-title":"Congr. Numer"},{"key":"10.1016\/S1571-0653(04)00062-9_NEWBIB19","first-page":"21","article-title":"Fault tolerant routing in split-stars and alternating group graphs","volume":"139","author":"Cheng","year":"1999","journal-title":"Congr. Numer"},{"key":"10.1016\/S1571-0653(04)00062-9_NEWBIB20","series-title":"Increasing the connectivity of star graphs. Technical Report 1999\u20135","author":"Cheng","year":"1999"},{"key":"10.1016\/S1571-0653(04)00062-9_NEWBIB21","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1016\/S0020-0190(99)00155-6","article-title":"On the Day-Tripathi orientation of the star graphs: connectivity","volume":"73","author":"Cheng","year":"2000","journal-title":"Inform. Proc. Lett"},{"key":"10.1016\/S1571-0653(04)00062-9_NEWBIB22","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1002\/(SICI)1097-0037(200003)35:2<139::AID-NET4>3.0.CO;2-E","article-title":"Orienting split-stars and alternating group graphs","volume":"35","author":"Cheng","year":"2000","journal-title":"Networks"},{"key":"10.1016\/S1571-0653(04)00062-9_NEWBIB23","series-title":"Orienting the arrangement graphs. Technical Report 2000\u20131","author":"Cheng","year":"2000"},{"key":"10.1016\/S1571-0653(04)00062-9_NEWBIB24","unstructured":"E. Cheng, M.J. Lipman, and H.A. Park. Super connectivity of star graphs, alternating group graphs and split-stars. Ars Combinatoria (to appear)."},{"key":"10.1016\/S1571-0653(04)00062-9_NEWBIB25","first-page":"490","article-title":"Uni-directional alternating group graphs","volume":"959","author":"Chern","year":"1995"},{"key":"10.1016\/S1571-0653(04)00062-9_NEWBIB26","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1016\/0020-0190(95)00162-1","article-title":"The (n, k)-star graph: A generalized star graph","volume":"56","author":"Chiang","year":"1995","journal-title":"Inform. Proc. Lett"},{"key":"10.1016\/S1571-0653(04)00062-9_NEWBIB27","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1016\/S0020-0190(98)00052-0","article-title":"On the arrangement graph","volume":"66","author":"Chiang","year":"1998","journal-title":"Inform. Proc. Lett"},{"key":"10.1016\/S1571-0653(04)00062-9_NEWBIB28","doi-asserted-by":"crossref","unstructured":"C.H. Chou and D.H.C. Du. Unidirectional hypercubes. Proc. Supercompiting'90, pages 254\u2013263, 1990.","DOI":"10.1109\/SUPERC.1990.130028"},{"key":"10.1016\/S1571-0653(04)00062-9_NEWBIB29","first-page":"23","article-title":"Tough graphs and hamiltonian circuits","volume":"8","author":"Chv\u00e1tal","year":"1972","journal-title":"Discrete Math"},{"key":"10.1016\/S1571-0653(04)00062-9_NEWBIB30","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0166-218X(93)E0145-O","article-title":"Vertex-symmetric digraphs with small diameter","volume":"58","author":"Comellas","year":"1995","journal-title":"Discrete Appl. Math"},{"key":"10.1016\/S1571-0653(04)00062-9_NEWBIB31","series-title":"Graph theory, combinatorics, and algorithms","first-page":"1111","article-title":"The tenacity of a graph","author":"Cozzens","year":"1995"},{"key":"10.1016\/S1571-0653(04)00062-9_NEWBIB32","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1145\/3828.3829","article-title":"Optimal attack and reinforcement of a network","volume":"32","author":"Cunningham","year":"1985","journal-title":"J. ACM"},{"key":"10.1016\/S1571-0653(04)00062-9_NEWBIB33","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1016\/0020-0190(92)90030-Y","article-title":"Arrangement graphs: a class of generalized star graphs","volume":"42","author":"Day","year":"1992","journal-title":"Inform. Proc. Lett"},{"key":"10.1016\/S1571-0653(04)00062-9_NEWBIB34","first-page":"1002","article-title":"Embedding of cycles in arrangement graphs","volume":"12","author":"Day","year":"1992","journal-title":"IEEE Trans. on Computers"},{"key":"10.1016\/S1571-0653(04)00062-9_NEWBIB35","doi-asserted-by":"crossref","unstructured":"K. Day and A. Tripathi. Embedding grids, hypercubes, and trees in arrangement graphs. Proc. Int'l Conf. Parallel Processing, pages III\u201365\u2013III\u201372, 1993.","DOI":"10.1109\/ICPP.1993.76"},{"key":"10.1016\/S1571-0653(04)00062-9_NEWBIB36","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1016\/0020-0190(93)90013-Y","article-title":"Unidirectional star graphs","volume":"45","author":"Day","year":"1993","journal-title":"Inform. Proc. Lett"},{"key":"10.1016\/S1571-0653(04)00062-9_NEWBIB37","first-page":"35","article-title":"Characterization of parallel paths in arrangement graphs","volume":"25","author":"Day","year":"1998","journal-title":"Kuwait J. Sci. & Eng"},{"issue":"3","key":"10.1016\/S1571-0653(04)00062-9_NEWBIB38","doi-asserted-by":"crossref","first-page":"439","DOI":"10.1007\/s101070050031","volume":"84","year":"1999","journal-title":"Math. Prog. (Series B)"},{"key":"10.1016\/S1571-0653(04)00062-9_NEWBIB39","series-title":"Combinatorial Structures and Their Applications","first-page":"69","article-title":"Submodular functions, matroids, and certain polyhedra","author":"Edmonds","year":"1970"},{"key":"10.1016\/S1571-0653(04)00062-9_NEWBIB40","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1016\/0020-0190(93)90043-9","article-title":"Fault tolerant routing in the star and pancake interconnection networks","volume":"45","author":"Gargano","year":"1993","journal-title":"Inform. Proc. Lett"},{"key":"10.1016\/S1571-0653(04)00062-9_NEWBIB41","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1016\/S0020-0190(98)00121-5","article-title":"An efficient algorithm for k-pairwise disjoint paths in star graphs","volume":"67","author":"Gu","year":"1998","journal-title":"Inform. Proc. Lett"},{"key":"10.1016\/S1571-0653(04)00062-9_NEWBIB42","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1002\/(SICI)1097-0037(200001)35:1<83::AID-NET7>3.0.CO;2-D","article-title":"Cluster fault-tolerant routing in star graphs","volume":"35","author":"Gu","year":"2000","journal-title":"Networks"},{"key":"10.1016\/S1571-0653(04)00062-9_NEWBIB43","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/0020-0190(83)90031-5","article-title":"Connectivity and edge disjoint spanning trees","volume":"16","author":"Gusfield","year":"1983","journal-title":"Inform. Proc. Lett"},{"key":"10.1016\/S1571-0653(04)00062-9_NEWBIB44","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1109\/71.755822","article-title":"Fault-free hamiltonian cycles in faulty arrangement graphs","volume":"10","author":"Hsieh","year":"1999","journal-title":"IEEE Trans. on Parallel and Distributed Systems"},{"key":"10.1016\/S1571-0653(04)00062-9_NEWBIB45","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1002\/net.3230230414","article-title":"A new class of interconnection networks based on the alternating group","volume":"23","author":"Jwo","year":"1993","journal-title":"Networks"},{"key":"10.1016\/S1571-0653(04)00062-9_NEWBIB46","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1002\/(SICI)1097-0037(199812)32:4<307::AID-NET7>3.0.CO;2-5","article-title":"On container length and connectivity in unidirectional hypercubes","volume":"32","author":"Jwo","year":"1998","journal-title":"Networks"},{"key":"10.1016\/S1571-0653(04)00062-9_NEWBIB47","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1002\/net.1975.5.1.45","article-title":"On the complexity of combinatorial problems","volume":"5","author":"Karp","year":"1975","journal-title":"Networks"},{"issue":"4","key":"10.1016\/S1571-0653(04)00062-9_NEWBIB48","doi-asserted-by":"crossref","first-page":"389","DOI":"10.1109\/71.149958","article-title":"Optimal broadcasting on the star graphs","volume":"3","author":"Mendia","year":"1992","journal-title":"IEEE Trans. on Parallel and Dist. Sys"},{"key":"10.1016\/S1571-0653(04)00062-9_NEWBIB49","doi-asserted-by":"crossref","first-page":"445","DOI":"10.1112\/jlms\/s1-36.1.445","article-title":"Edge disjoint spanning trees in finite graphs","volume":"36","author":"Nash-Williams","year":"1961","journal-title":"J. London Math. Soc"},{"key":"10.1016\/S1571-0653(04)00062-9_NEWBIB50","doi-asserted-by":"crossref","first-page":"458","DOI":"10.1109\/TC.1977.1674863","article-title":"The indirect binary n-cube microprocessor array","volume":"26","author":"Pease","year":"1977","journal-title":"IEEE Trans. Comput"},{"issue":"5","key":"10.1016\/S1571-0653(04)00062-9_NEWBIB51","first-page":"30","article-title":"The cube-connected cycles: A versatile network for parallel computation","volume":"24","author":"Preparata","year":"1991","journal-title":"Comm. ACM"},{"key":"10.1016\/S1571-0653(04)00062-9_NEWBIB52","doi-asserted-by":"crossref","first-page":"867","DOI":"10.1109\/12.2234","article-title":"Topological properties of hypercubes","volume":"37","author":"Saad","year":"1988","journal-title":"IEEE Trans. Comput"},{"key":"10.1016\/S1571-0653(04)00062-9_NEWBIB53","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1145\/2465.2467","article-title":"The cosmic cube","volume":"28","author":"Seitz","year":"1985","journal-title":"Comm. ACM"},{"key":"10.1016\/S1571-0653(04)00062-9_NEWBIB54","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1016\/0020-0190(93)90119-T","article-title":"The 4-star graph is not a subgraph of any hypercube","volume":"37","author":"Shen","year":"1993","journal-title":"Inform. Proc. Lett"},{"issue":"6","key":"10.1016\/S1571-0653(04)00062-9_NEWBIB55","doi-asserted-by":"crossref","first-page":"653","DOI":"10.1109\/71.388046","article-title":"An optimal broadcasting algorithm without message redunancy in star graphs","volume":"6","author":"Sheu","year":"1995","journal-title":"IEEE Trans. on Parallel and Dist. Sys"},{"key":"10.1016\/S1571-0653(04)00062-9_NEWBIB56","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1002\/(SICI)1097-0037(199905)33:3<221::AID-NET8>3.0.CO;2-K","article-title":"Congestion-free, dilation-2 embedding of complex binary trees into star graphs","volume":"33","author":"Tseng","year":"1999","journal-title":"Networks"},{"key":"10.1016\/S1571-0653(04)00062-9_NEWBIB57","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1112\/jlms\/s1-36.1.221","article-title":"On the problem of decomposing a graph into n connected factors","volume":"36","author":"Tutte","year":"1961","journal-title":"J. London Math. Soc"},{"key":"10.1016\/S1571-0653(04)00062-9_NEWBIB58","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1215\/S0012-7094-68-03523-0","article-title":"On the existence of certain disjoint arcs in graphs","volume":"35","author":"Watkins","year":"1968","journal-title":"Duke Math J"},{"key":"10.1016\/S1571-0653(04)00062-9_NEWBIB59","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/S0020-0190(98)00133-1","article-title":"VLSI layouts of complete graphs and star graphs","volume":"68","author":"Yeh","year":"1998","journal-title":"Inform. Process. Lett"}],"container-title":["Electronic Notes in Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S1571065304000629?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S1571065304000629?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,4,3]],"date-time":"2020-04-03T10:43:30Z","timestamp":1585910610000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S1571065304000629"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002,7]]},"references-count":59,"alternative-id":["S1571065304000629"],"URL":"https:\/\/doi.org\/10.1016\/s1571-0653(04)00062-9","relation":{},"ISSN":["1571-0653"],"issn-type":[{"value":"1571-0653","type":"print"}],"subject":[],"published":{"date-parts":[[2002,7]]}}}