{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T12:48:16Z","timestamp":1759063696739},"reference-count":21,"publisher":"Wiley","issue":"7","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":4758,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1993,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Motivated by the study of large graphs with given degree and diameter, and the recent interest in the design of highly symmetric interconnection networks (e.g., the study of Cayley digraphs), we are led to the search for large vertex symmetric digraphs with given degree and diameter. The main result of this paper is the construction of a new class of vertex symmetric directed graphs, \u0393<jats:sub>\u03b4<\/jats:sub><jats:italic>(D)<\/jats:italic> (\u03b4 \u2265 <jats:italic>D<\/jats:italic>) that have degree \u03b4, diameter <jats:italic>D<\/jats:italic>, and (\u03b4 + 1)\u03b4 \u2026 (\u03b4 \u2013 <jats:italic>D<\/jats:italic> + 2) vertices. The graphs \u0393<jats:sub>\u03b4<\/jats:sub><jats:italic>(D)<\/jats:italic> are first found in the notation of Cayley coset digraphs. Then, we discover that they have a very simple representation in terms of sequences like the commonly studied networks such as the hypercube, de Bruijn graphs, and Kautz graphs. Based on the sequence representation, we give a simple shortest\u2010path routing scheme. We also show that the average distance in our digraph \u0393<jats:sub>\u03b4<\/jats:sub><jats:italic>(D)<\/jats:italic> is very close to its diameter <jats:italic>D<\/jats:italic>. As a consequence, it follows that the natural routing scheme, which is even simpler than the shortest\u2010path routing, is nearly optimal on an average basis. \u00a9 <jats:italic>1993 by John Wiley &amp; Sons, Inc.<\/jats:italic><\/jats:p>","DOI":"10.1002\/net.3230230707","type":"journal-article","created":{"date-parts":[[2007,5,12]],"date-time":"2007-05-12T16:48:59Z","timestamp":1178988539000},"page":"641-649","source":"Crossref","is-referenced-by-count":36,"title":["Cycle prefix digraphs for symmetric interconnection networks"],"prefix":"10.1002","volume":"23","author":[{"given":"Vance","family":"Faber","sequence":"first","affiliation":[]},{"given":"James W.","family":"Moore","sequence":"additional","affiliation":[]},{"given":"William Y. C.","family":"Chen","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1109\/12.21148"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-54029-6_192"},{"key":"e_1_2_1_4_2","unstructured":"Discrete Appl. Math. 1992 37\/38 Interconnection Networks"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/0743-7315(86)90008-0"},{"key":"e_1_2_1_6_2","first-page":"279","volume-title":"Proceedings of the First European Workshop on Hypercube and Distributed Computers","author":"Bermond J.\u2010C.","year":"1989"},{"key":"e_1_2_1_7_2","unstructured":"W. Y. C.ChenandV.Faber The automorphism group of the cycle prefix digraph. Preprint (1992)."},{"key":"e_1_2_1_8_2","unstructured":"W. Y. C.Chen V.Faber andE.Knill Restricted routing and wide diameter of cycle prefix networks. Preprint Los Alamos National Laboratory (1993)."},{"key":"e_1_2_1_9_2","unstructured":"F.ComellasandM. A.Fiol Vertex symmetric digraphs with small diameter. Preprint (1992)."},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-21943-0"},{"key":"e_1_2_1_11_2","unstructured":"M. J.Dinneen Algebraic methods for efficient network constructions. Master Thesis Department of Computer Science University of Victoria Victoria B. C. Canada (1991)."},{"key":"e_1_2_1_12_2","unstructured":"V.Faber Global communication algorithms for hypercubes and other Cayley coset graphs. Technical Report LA\u2010UR\u201087\u20103136 Los Alamos National Laboratory (1987)."},{"key":"e_1_2_1_13_2","unstructured":"V.FaberandJ.Moore High\u2010degree low\u2010diameter interconnection networks with vertex symmetry: The directed case. Technical Report LA\u2010UR\u201088\u20101051 Los Alamos National Laboratory (1988)."},{"key":"e_1_2_1_14_2","unstructured":"V.FaberandJ.Moore Interconnection networks. US Patent 5 125 076 (June 23 1992)."},{"key":"e_1_2_1_15_2","unstructured":"D. M.Gordon Parallel sorting on Cayley graphs. Preprint (1990)."},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(92)90138-Z"},{"key":"e_1_2_1_17_2","unstructured":"D. F. Hsu Ed. Interconnection Networks and Algorithms. Special IssueNetworks to appear."},{"key":"e_1_2_1_18_2","unstructured":"D. F.Hsu On container width and length in graphs groups and networks. Preprint (1992)."},{"key":"e_1_2_1_19_2","unstructured":"M.JiangandF.Ruskey Determining the Hamilton\u2010connectedness of certain vertex\u2010transitive graphs. Technical Report DCS\u2010202\u2010IR Department of Computer Science University of Victoria Victoria B.C. Canada (1992)."},{"key":"e_1_2_1_20_2","unstructured":"E.Knill The connectivity of Cayley coset graphs. Preprint (1992)."},{"key":"e_1_2_1_21_2","volume-title":"The Art of Computer Programming","author":"Knuth D. E.","year":"1973"},{"key":"e_1_2_1_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01304186"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230230707","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230230707","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,24]],"date-time":"2023-10-24T21:45:43Z","timestamp":1698183943000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230230707"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,10]]},"references-count":21,"journal-issue":{"issue":"7","published-print":{"date-parts":[[1993,10]]}},"alternative-id":["10.1002\/net.3230230707"],"URL":"https:\/\/doi.org\/10.1002\/net.3230230707","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993,10]]}}}