Subgraphs with a positive minimum semidegree in digraphs with large outdegree
Grzesik, Andrzej1; Rödl, Vojtěch2; Volec, Jan3
1 Faculty of Mathematics and Computer Science, Jagiellonian University, Prof. St. Łojasiewicza 6, 30-348 Kraków (Poland)
2 Department of Mathematics, Emory University, Atlanta (USA)
3 Department of Theoretical Computer Science, Faculty of Information Technology, Czech Technical University in Prague, Thákurova 9, Prague, 160 00 (Czech Republic)
Innovations in Graph Theory, Volume 2 (2025), pp. 301-312

We prove that every $n$-vertex directed graph $G$ with the minimum outdegree $\delta ^+(G) = d$ contains a subgraph $H$ satisfying

\[ \min \left\lbrace \delta ^+(H), \delta ^-(H) \right\rbrace \ge \frac{d(d+1)}{2n} \,. \]

We also show that if $d = o(n)$ then this bound is asymptotically best possible.

Received:
Accepted:
Published online:
DOI: 10.5802/igt.14

Grzesik, Andrzej 1; Rödl, Vojtěch 2; Volec, Jan 3

1 Faculty of Mathematics and Computer Science, Jagiellonian University, Prof. St. Łojasiewicza 6, 30-348 Kraków (Poland)
2 Department of Mathematics, Emory University, Atlanta (USA)
3 Department of Theoretical Computer Science, Faculty of Information Technology, Czech Technical University in Prague, Thákurova 9, Prague, 160 00 (Czech Republic)
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights 
@article{IGT_2025__2__301_0,
     author = {Grzesik, Andrzej and R\"odl, Vojt\v{e}ch and Volec, Jan},
     title = {Subgraphs with a positive minimum semidegree in digraphs with large outdegree},
     journal = {Innovations in Graph Theory},
     pages = {301--312},
     year = {2025},
     publisher = {Stichting Innovations in Graph Theory},
     volume = {2},
     doi = {10.5802/igt.14},
     language = {en},
     url = {https://igt.centre-mersenne.org/articles/10.5802/igt.14/}
}
TY  - JOUR
AU  - Grzesik, Andrzej
AU  - Rödl, Vojtěch
AU  - Volec, Jan
TI  - Subgraphs with a positive minimum semidegree in digraphs with large outdegree
JO  - Innovations in Graph Theory
PY  - 2025
SP  - 301
EP  - 312
VL  - 2
PB  - Stichting Innovations in Graph Theory
UR  - https://igt.centre-mersenne.org/articles/10.5802/igt.14/
DO  - 10.5802/igt.14
LA  - en
ID  - IGT_2025__2__301_0
ER  - 
%0 Journal Article
%A Grzesik, Andrzej
%A Rödl, Vojtěch
%A Volec, Jan
%T Subgraphs with a positive minimum semidegree in digraphs with large outdegree
%J Innovations in Graph Theory
%D 2025
%P 301-312
%V 2
%I Stichting Innovations in Graph Theory
%U https://igt.centre-mersenne.org/articles/10.5802/igt.14/
%R 10.5802/igt.14
%G en
%F IGT_2025__2__301_0
Grzesik, Andrzej; Rödl, Vojtěch; Volec, Jan. Subgraphs with a positive minimum semidegree in digraphs with large outdegree. Innovations in Graph Theory, Volume 2 (2025), pp. 301-312. doi: 10.5802/igt.14

[1] Alon, Noga; Shapira, Asaf Testing subgraphs in directed graphs, J. Comput. Syst. Sci., Volume 69 (2004) no. 3, pp. 354-382 | DOI | Zbl | MR

[2] Bang-Jensen, Jørgen; Gutin, Gregory Z. Digraphs: theory, algorithms and applications, Springer, 2008 | MR

[3] Caccetta, L.; Häggkvist, R. On minimal digraphs with given girth, Congr. Numerantium, Volume 21 (1978), pp. 181-187 | Zbl

[4] Chvátal, V.; Szemerédi, E. Short cycles in directed graphs, J. Comb. Theory, Ser. B, Volume 35 (1983) no. 3, pp. 323-327 | DOI | Zbl | MR

[5] Erdős, Paul On an extremal problem in graph theory, Colloq. Math., Volume 13 (1964), pp. 251-254 | DOI | Zbl | MR

[6] Erdős, Paul On extremal problems of graphs and generalized graphs, Isr. J. Math., Volume 2 (1964) no. 3, pp. 183-190 | Zbl | MR | DOI

[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 | DOI | MR | Zbl

[8] Shen, Jian Directed Triangles in Digraphs, J. Comb. Theory, Ser. B, Volume 74 (1998) no. 2, pp. 405-407 | DOI | Zbl | MR

Cited by Sources: