{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T16:39:19Z","timestamp":1740155959112,"version":"3.37.3"},"reference-count":28,"publisher":"World Scientific Pub Co Pte Ltd","issue":"05","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Math. Algorithm. Appl."],"published-print":{"date-parts":[[2017,10]]},"abstract":"<jats:p> A set of vertices of a graph whose removal leaves an acyclic graph is referred as a decycling set, or a feedback vertex set, of the graph. The minimum cardinality of a decycling set of a graph [Formula: see text] is referred to as the decycling number of [Formula: see text]. For [Formula: see text], the generalized de Bruijn digraph [Formula: see text] is defined by congruence equations as follows: [Formula: see text] and [Formula: see text]. In this paper, we give a systematic method to find a decycling set of [Formula: see text] and give a new upper bound that improve the best known results. By counting the number of vertex-disjoint cycles with the idea of constrained necklaces, we obtain new lower bounds on the decycling number of generalized de Bruijn digraphs. <\/jats:p>","DOI":"10.1142\/s1793830917500628","type":"journal-article","created":{"date-parts":[[2017,8,8]],"date-time":"2017-08-08T03:40:11Z","timestamp":1502163611000},"page":"1750062","source":"Crossref","is-referenced-by-count":0,"title":["New bounds on the decycling number of generalized de Bruijn digraphs"],"prefix":"10.1142","volume":"09","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1023-5308","authenticated-orcid":false,"given":"Jyhmin","family":"Kuo","sequence":"first","affiliation":[{"name":"Chen-Te Senior High School, Hsin Chu 30047, Taiwan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hung-Lin","family":"Fu","sequence":"additional","affiliation":[{"name":"Department of Applied Mathematics, National Chiao Tung University, Hsin Chu 30050, Taiwan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2017,11,2]]},"reference":[{"key":"S1793830917500628BIB001","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796305109"},{"key":"S1793830917500628BIB002","first-page":"285","volume":"25","author":"Bau S.","year":"2002","journal-title":"Australas. J. Combin."},{"key":"S1793830917500628BIB003","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0118(199705)25:1<59::AID-JGT4>3.0.CO;2-H"},{"key":"S1793830917500628BIB004","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(86)90028-6"},{"key":"S1793830917500628BIB005","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-3023-4_4"},{"key":"S1793830917500628BIB006","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(00)00127-7"},{"volume-title":"Concrete Mathematics","year":"1988","author":"Graham R. L.","key":"S1793830917500628BIB007"},{"key":"S1793830917500628BIB008","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1981.1675809"},{"key":"S1793830917500628BIB009","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1983.1676323"},{"key":"S1793830917500628BIB010","doi-asserted-by":"crossref","first-page":"618","DOI":"10.2307\/2271828","volume":"40","author":"Karp R. M.","year":"1975","journal-title":"J. Symbolic Logic"},{"key":"S1793830917500628BIB011","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1137"},{"key":"S1793830917500628BIB012","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(94)00133-2"},{"key":"S1793830917500628BIB013","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2014.09.013"},{"key":"S1793830917500628BIB014","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2007.08.007"},{"key":"S1793830917500628BIB015","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(98)00043-2"},{"key":"S1793830917500628BIB016","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00055-X"},{"key":"S1793830917500628BIB017","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-003-0529-9"},{"key":"S1793830917500628BIB018","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(94)90090-6"},{"key":"S1793830917500628BIB019","volume-title":"Operating System Concepts","author":"Silberschatz A.","year":"2003","edition":"6"},{"key":"S1793830917500628BIB020","doi-asserted-by":"publisher","DOI":"10.1002\/net.20067"},{"key":"S1793830917500628BIB021","doi-asserted-by":"publisher","DOI":"10.1145\/3149.3159"},{"key":"S1793830917500628BIB022","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2003.11.001"},{"key":"S1793830917500628BIB023","first-page":"147","volume":"116","author":"Wang L.","year":"2014","journal-title":"Ars Combin."},{"key":"S1793830917500628BIB024","doi-asserted-by":"publisher","DOI":"10.1016\/j.camwa.2009.10.021"},{"key":"S1793830917500628BIB025","first-page":"3","volume":"52","author":"Xu X.","year":"2012","journal-title":"Australas. J. Combin."},{"key":"S1793830917500628BIB026","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2006.09.010"},{"key":"S1793830917500628BIB027","doi-asserted-by":"publisher","DOI":"10.11650\/twjm\/1500406287"},{"key":"S1793830917500628BIB028","first-page":"107","volume":"79","author":"Xu X.","year":"2009","journal-title":"Util. Math."}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S1793830917500628","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T01:23:49Z","timestamp":1565141029000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S1793830917500628"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,10]]},"references-count":28,"journal-issue":{"issue":"05","published-online":{"date-parts":[[2017,11,2]]},"published-print":{"date-parts":[[2017,10]]}},"alternative-id":["10.1142\/S1793830917500628"],"URL":"https:\/\/doi.org\/10.1142\/s1793830917500628","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"type":"print","value":"1793-8309"},{"type":"electronic","value":"1793-8317"}],"subject":[],"published":{"date-parts":[[2017,10]]}}}