{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T12:08:00Z","timestamp":1742386080480},"reference-count":7,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2000,7,1]],"date-time":"2000-07-01T00:00:00Z","timestamp":962409600000},"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":[[2000,7]]},"DOI":"10.1016\/s1571-0653(05)80139-8","type":"journal-article","created":{"date-parts":[[2005,5,1]],"date-time":"2005-05-01T07:08:52Z","timestamp":1114931332000},"page":"112-115","source":"Crossref","is-referenced-by-count":4,"special_numbering":"C","title":["Recognizing Recursive Circulant Graphs (Extended Abstract)"],"prefix":"10.1016","volume":"5","author":[{"given":"Guillaume","family":"Fertin","sequence":"first","affiliation":[]},{"given":"Andr\u00e9","family":"Raspaud","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/S1571-0653(05)80139-8_BIB1","series-title":"In 25th International Workshop on Graph-Theoretic Concepts in Computer Science (WG'99), volume 1665 of Lecture Notes in Computer Science","first-page":"215","article-title":"Recognizing bipartite incident-graphs of circulant digraphs","author":"Cohen","year":"1999"},{"key":"10.1016\/S1571-0653(05)80139-8_BIB2","first-page":"63","article-title":"Families of graphs having broadcasting and gossiping properties","volume":"1517","author":"Fertin","year":"1998","journal-title":"In Proc. of the 24th International Workshop on Graph-Theoretic Concepts in Computer Science (WG'98), Smolenice. LNCS"},{"key":"10.1016\/S1571-0653(05)80139-8_BIB3","author":"Fertin","year":"1998","journal-title":"A survey on Knodel graphs. Technical report, Laboratoire Bordelais de Recherche en Informatique"},{"key":"10.1016\/S1571-0653(05)80139-8_BIB4","first-page":"227","article-title":"Routing in recursive circulant graphs: Edge forwarding index and hamiltonian decomposition","volume":"1517","author":"Gauyacq","year":"1998","journal-title":"In Proc. of the 24th International Workshop on Graph-Theoretic Concepts in Computer Science (WG'98), Smolenice. LNCS"},{"key":"10.1016\/S1571-0653(05)80139-8_BIB5","series-title":"Communications Vagabondes et Simulation","article-title":"Graphes R\u00e9cursifs Circulants : Structure et Communications","author":"Micheneau","year":"1996"},{"key":"10.1016\/S1571-0653(05)80139-8_BIB6","unstructured":"J-H. Park and K-Y. Chwa. Recursive circulants and their embeddings among hypercubes. Manuscript. Submitted for Publication."},{"key":"10.1016\/S1571-0653(05)80139-8_BIB7","unstructured":"as a new topology for interconnection networks. Recursive circulant graphs G(N, d) are circulant graphs with N nodes and with jumps of powers of d. A subfamily of recursive circulant graphs (more precisely, G(2k, 4)) is of same order and degree than the hypercube of dimension k, with sometimes better parameters, such as diameter [PC94, GMR98]. Embeddings among recursive circulant graphs, hypercubes and Knodel graphs of order 2k have also been studied in [PC, FR98b]. Here, following a question raised in [CFG99], we give, thanks to a sharp structural analysis of such graphs, an O(cdm+2 \u00b7 (2m)d) algorithm to determine if a given graph is a recursive circulant graph of the form G(cdm,d), for any d \u2265 3, except in the case where c is even while d is odd. Notably, in the case where d = O(1), this gives an O(N\u00b7(log(N))O(1)) algorithm, with N = cdm. Moreover, applying this algorithm to recursive circulant graphs G(2k,4) gives us an O(1k \u00b7 k4) recognition algorithm for such graphs."}],"container-title":["Electronic Notes in Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S1571065305801398?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S1571065305801398?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,1,26]],"date-time":"2019-01-26T14:58:07Z","timestamp":1548514687000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S1571065305801398"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,7]]},"references-count":7,"alternative-id":["S1571065305801398"],"URL":"https:\/\/doi.org\/10.1016\/s1571-0653(05)80139-8","relation":{},"ISSN":["1571-0653"],"issn-type":[{"value":"1571-0653","type":"print"}],"subject":[],"published":{"date-parts":[[2000,7]]}}}