{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,25]],"date-time":"2026-01-25T11:04:08Z","timestamp":1769339048287,"version":"3.49.0"},"reference-count":8,"publisher":"MathDoc\/Centre Mersenne","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>\n                    We prove that every\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mi>n<\/mml:mi>\n                    <\/mml:math>\n                    -vertex directed graph\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mi>G<\/mml:mi>\n                    <\/mml:math>\n                    with the minimum outdegree\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mrow>\n                        <mml:msup>\n                          <mml:mi>\u03b4<\/mml:mi>\n                          <mml:mo>+<\/mml:mo>\n                        <\/mml:msup>\n                        <mml:mrow>\n                          <mml:mo>(<\/mml:mo>\n                          <mml:mi>G<\/mml:mi>\n                          <mml:mo>)<\/mml:mo>\n                        <\/mml:mrow>\n                        <mml:mo>=<\/mml:mo>\n                        <mml:mi>d<\/mml:mi>\n                      <\/mml:mrow>\n                    <\/mml:math>\n                    contains a subgraph\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mi>H<\/mml:mi>\n                    <\/mml:math>\n                    satisfying\n                  <\/jats:p>\n                  <jats:p>\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"block\">\n                      <mml:mrow>\n                        <mml:mo form=\"prefix\" movablelimits=\"true\">min<\/mml:mo>\n                        <mml:mfenced close=\"}\" open=\"{\" separators=\"\">\n                          <mml:msup>\n                            <mml:mi>\u03b4<\/mml:mi>\n                            <mml:mo>+<\/mml:mo>\n                          <\/mml:msup>\n                          <mml:mrow>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:mi>H<\/mml:mi>\n                            <mml:mo>)<\/mml:mo>\n                          <\/mml:mrow>\n                          <mml:mo>,<\/mml:mo>\n                          <mml:msup>\n                            <mml:mi>\u03b4<\/mml:mi>\n                            <mml:mo>-<\/mml:mo>\n                          <\/mml:msup>\n                          <mml:mrow>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:mi>H<\/mml:mi>\n                            <mml:mo>)<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:mfenced>\n                        <mml:mo>\u2265<\/mml:mo>\n                        <mml:mfrac>\n                          <mml:mrow>\n                            <mml:mi>d<\/mml:mi>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:mi>d<\/mml:mi>\n                            <mml:mo>+<\/mml:mo>\n                            <mml:mn>1<\/mml:mn>\n                            <mml:mo>)<\/mml:mo>\n                          <\/mml:mrow>\n                          <mml:mrow>\n                            <mml:mn>2<\/mml:mn>\n                            <mml:mi>n<\/mml:mi>\n                          <\/mml:mrow>\n                        <\/mml:mfrac>\n                        <mml:mspace width=\"0.166667em\"\/>\n                        <mml:mo>.<\/mml:mo>\n                      <\/mml:mrow>\n                    <\/mml:math>\n                  <\/jats:p>\n                  <jats:p>\n                    We also show that if\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mrow>\n                        <mml:mi>d<\/mml:mi>\n                        <mml:mo>=<\/mml:mo>\n                        <mml:mi>o<\/mml:mi>\n                        <mml:mo>(<\/mml:mo>\n                        <mml:mi>n<\/mml:mi>\n                        <mml:mo>)<\/mml:mo>\n                      <\/mml:mrow>\n                    <\/mml:math>\n                    then this bound is asymptotically best possible.\n                  <\/jats:p>","DOI":"10.5802\/igt.14","type":"journal-article","created":{"date-parts":[[2025,11,26]],"date-time":"2025-11-26T16:24:46Z","timestamp":1764174286000},"page":"301-312","source":"Crossref","is-referenced-by-count":0,"title":["Subgraphs with a positive minimum semidegree in digraphs with large outdegree"],"prefix":"10.5802","volume":"2","author":[{"given":"Andrzej","family":"Grzesik","sequence":"first","affiliation":[{"name":"Faculty of Mathematics and Computer Science, Jagiellonian University, Prof.\u00a0St.\u00a0\u0141ojasiewicza 6, 30-348 Krak\u00f3w (Poland)"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vojt\u011bch","family":"R\u00f6dl","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Emory University, Atlanta (USA)"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jan","family":"Volec","sequence":"additional","affiliation":[{"name":"Department of Theoretical Computer Science, Faculty of Information Technology, Czech Technical University in Prague, Th\u00e1kurova 9, Prague, 160 00 (Czech Republic)"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"3842","published-online":{"date-parts":[[2025,11,26]]},"reference":[{"issue":"3","key":"key2025121216553547129_1","doi-asserted-by":"publisher","first-page":"354","DOI":"10.1016\/j.jcss.2004.04.008","article-title":"Testing subgraphs in directed graphs","volume":"69","author":"Alon, Noga","year":"2004","unstructured":"[1] Alon, Noga; Shapira, Asaf Testing subgraphs in directed graphs, J. Comput. Syst. Sci., Volume 69 (2004) no. 3, pp. 354-382","journal-title":"J. Comput. Syst. Sci."},{"key":"key2025121216553547129_2","author":"Bang-Jensen, J\u00f8rgen","year":"2008","unstructured":"[2] Bang-Jensen, J\u00f8rgen; Gutin, Gregory Z. Digraphs: theory, algorithms and applications, Springer, 2008","journal-title":"Digraphs: theory, algorithms and applications"},{"key":"key2025121216553547129_3","first-page":"181","article-title":"On minimal digraphs with given girth","volume":"21","author":"Caccetta, L.","year":"1978","unstructured":"[3] Caccetta, L.; H\u00e4ggkvist, R. On minimal digraphs with given girth, Congr. Numerantium, Volume 21 (1978), pp. 181-187","journal-title":"Congr. Numerantium"},{"issue":"3","key":"key2025121216553547129_4","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1016\/0095-8956(83)90059-X","article-title":"Short cycles in directed graphs","volume":"35","author":"Chv\u00e1tal, V.","year":"1983","unstructured":"[4] Chv\u00e1tal, V.; Szemer\u00e9di, E. Short cycles in directed graphs, J. Comb. Theory, Ser. B, Volume 35 (1983) no. 3, pp. 323-327","journal-title":"J. Comb. Theory, Ser. B"},{"key":"key2025121216553547129_5","doi-asserted-by":"publisher","first-page":"251","DOI":"10.4064\/cm-13-2-251-254","article-title":"On an extremal problem in graph theory","volume":"13","author":"Erd\u0151s, Paul","year":"1964","unstructured":"[5] Erd\u0151s, Paul On an extremal problem in graph theory, Colloq. Math., Volume 13 (1964), pp. 251-254","journal-title":"Colloq. Math."},{"issue":"3","key":"key2025121216553547129_6","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1007\/BF02759942","article-title":"On extremal problems of graphs and generalized graphs","volume":"2","author":"Erd\u0151s, Paul","year":"1964","unstructured":"[6] Erd\u0151s, Paul On extremal problems of graphs and generalized graphs, Isr. J. Math., Volume 2 (1964) no. 3, pp. 183-190","journal-title":"Isr. J. Math."},{"issue":"6","key":"key2025121216553547129_7","doi-asserted-by":"publisher","first-page":"859","DOI":"10.1017\/S0963548313000394","article-title":"Large feedback arc sets, high minimum degree subgraphs, and long cycles in Eulerian digraphs","volume":"22","author":"Huang, Hao","year":"2013","unstructured":"[7] Huang, Hao; Ma, Jie; Shapira, Asaf; Sudakov, Benny; Yuster, Raphael Large feedback arc sets, high minimum degree subgraphs, and long cycles in Eulerian digraphs, Comb. Probab. Comput., Volume 22 (2013) no. 6, pp. 859-873","journal-title":"Comb. Probab. Comput."},{"issue":"2","key":"key2025121216553547129_8","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1006\/jctb.1998.1839","article-title":"Directed Triangles in Digraphs","volume":"74","author":"Shen, Jian","year":"1998","unstructured":"[8] Shen, Jian Directed Triangles in Digraphs, J. Comb. Theory, Ser. B, Volume 74 (1998) no. 2, pp. 405-407","journal-title":"J. Comb. Theory, Ser. B"}],"container-title":["Innovations in Graph Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/igt.centre-mersenne.org\/item\/10.5802\/igt.14.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,12]],"date-time":"2025-12-12T15:55:43Z","timestamp":1765554943000},"score":1,"resource":{"primary":{"URL":"https:\/\/igt.centre-mersenne.org\/articles\/10.5802\/igt.14\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,11,26]]},"references-count":8,"alternative-id":["10.5802\/igt.14"],"URL":"https:\/\/doi.org\/10.5802\/igt.14","relation":{},"ISSN":["3050-743X"],"issn-type":[{"value":"3050-743X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,11,26]]}}}