{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:45:28Z","timestamp":1787323528359,"version":"build-2736575974"},"reference-count":22,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"DOI":"10.13039\/501100005357","name":"Agent\u00fara na Podporu V\u00fdskumu a V\u00fdvoja","doi-asserted-by":"publisher","award":["APVV-15-0220"],"award-info":[{"award-number":["APVV-15-0220"]}],"id":[{"id":"10.13039\/501100005357","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100006109","name":"Vedeck\u00e1 Grantov\u00e1 Agent\u00fara M\u0160VVa\u0160 SR a SAV","doi-asserted-by":"publisher","award":["1\/0813\/18"],"award-info":[{"award-number":["1\/0813\/18"]}],"id":[{"id":"10.13039\/501100006109","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:p>The well-known shortest cycle cover conjecture suggests that every bridgeless graph $G$ can have its edges covered with a collection of cycles of total length not exceeding $\\frac75\\cdot|E(G)|$. This conjecture is particularly interesting for cubic graphs, where the largest values of the ratio between the length of a shortest cycle cover and the number of edges are known. The covering ratio 7\/5 is the best possible, being reached by the Petersen graph whose shortest cycle cover has length 21. There exist infinitely many cubic graphs with cyclic connectivity 2, as well as those with cyclic connectivity 3, whose covering ratio equals 7\/5. By contrast, all cyclically 4-edge-connected cubic graphs where the length of a shortest cycle cover is known have covering ratio close to the natural lower bound which equals 4\/3. In line with this observation, Brinkmannn et al. [ J. Combin. Theory Ser. B, 103 (2013), pp. 468--488] made a conjecture that every cyclically 4-edge-connected cubic graph has a cycle cover of length at most $\\frac43 m+o(m)$, where $m$ is the number of edges. We disprove this conjecture by exhibiting an infinite family of cyclically 4-edge-connected cubic graphs $G_k$, $k\\ge 2$, such that the length of a shortest cycle cover of each $G_k$ is at least $(\\frac43 + \\frac{1}{69})|E(G_k)|$.<\/jats:p>","DOI":"10.1137\/21m1399208","type":"journal-article","created":{"date-parts":[[2021,9,23]],"date-time":"2021-09-23T10:51:34Z","timestamp":1632394294000},"page":"2223-2233","source":"Crossref","is-referenced-by-count":2,"title":["Cubic Graphs with No Short Cycle Covers"],"prefix":"10.1137","volume":"35","author":[{"given":"Edita","family":"M\u00e1\u010dajov\u00e1","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Martin","family":"\u0160koviera","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2021,9,23]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.37236\/6008"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1137\/0606035"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(83)90056-4"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2013.05.001"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1137\/15M1045144"},{"key":"atypb6","first-page":"1247","volume":"42","author":"Chen F.","year":"2016","journal-title":"Bull. Iranian Math. Soc."},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.21778"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190180204"},{"key":"atypb9","doi-asserted-by":"crossref","unstructured":"G. Fan,\n                      Integer 4-flows and cycle covers\n                      , Combinatorica, 37 (2017), pp. 1097-1112.","DOI":"10.1007\/s00493-016-3379-9"},{"key":"atypb10","first-page":"457","volume":"4","author":"H\u00e4gglund J.","year":"2013","journal-title":"J. Comb."},{"key":"atypb11","first-page":"289","author":"Itai A.","year":"1978","journal-title":"Berlin"},{"key":"atypb12","first-page":"191","author":"Jackson B.","year":"1993","journal-title":"UK"},{"key":"atypb13","unstructured":"F. Jaeger,\n                      Private communication\n                      , 1985."},{"key":"atypb14","first-page":"71","author":"Jaeger F.","year":"1988","journal-title":"London"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(92)90018-S"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1137\/080717468"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1137\/19M1241866"},{"key":"atypb18","first-page":"481","volume":"45","author":"Nedela R.","year":"1995","journal-title":"Math. Slovaca"},{"key":"atypb19","unstructured":"A. Raspaud,\n                      Flots et couvertures par des cycles dans les graphes et les matro\u00ef des\n                      , Th\u00e8se de $3^{{\\`eme}}$ cycle, Universit\u00e9 de Grenoble, 1985."},{"key":"atypb20","doi-asserted-by":"crossref","first-page":"665","DOI":"10.1090\/S0002-9947-1984-0743738-4","volume":"284","author":"Robertson N.","year":"1984","journal-title":"Trans. Amer. Math. Soc."},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.21798"},{"key":"atypb22","unstructured":"C.Q. Zhang,\n                      Circuit Double Cover of Graphs\n                      , London Math. Soc. Lecture Note Ser. 399, Cambridge University Press, Cambridge, UK, 2012."}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/21M1399208","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:07:31Z","timestamp":1787321251000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/21M1399208"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":22,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1137\/21M1399208"],"URL":"https:\/\/doi.org\/10.1137\/21m1399208","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1]]}}}