Indexed by:
Abstract:
In 2006, Alon proposed a problem of characterizing all four-tuples (n, m, s, d) such that every digraph on n vertices of minimum out-degree at least s contains a subdigraph on m vertices of minimum out-degree at least d. He in particular asked whether there exists an absolute constant c such that every digraph on 2n vertices of minimum out-degree at least s contains a subdigraph on n vertices of minimum out-degree at least 2s - c? Recently, Steiner resolved this case in the negative by showing that for arbitrarily large n, there exists a tournament on 2n vertices of minimum out-degree s = n -1, in which the minimum outdegree of every subdigraph on n vertices is at most 2s - (21 + o(1)) log3s. In this paper, we study the above problem and present two new results. The first result is that for arbitrary large nand any integer alpha >= 2, there exists a digraph on alpha n vertices of minimum out-degree s = n -1 satisfying that the minimum out-degree of every subdigraph on n vertices is at most alpha s - (alpha 1 +o(1)) log alpha+1 s. The second result is that for arbitrary large nand any r >= 3, there exists a digraph on 2n vertices of girth rand minimum out-degree s satisfying that the minimum out-degree of every subdigraph on n vertices is at most 2 - ( 1 s 2 +o(1)) logrs if r is odd, and is at most 2s - (21 +o(1)) logr +1 s if r is even. (c) 2024 Elsevier B.V. All rights are reserved, including those for text and data mining, AI training, and similar technologies.
Keyword:
Reprint 's Address:
Email:
Version:
Source :
DISCRETE MATHEMATICS
ISSN: 0012-365X
Year: 2025
Issue: 3
Volume: 348
0 . 7 0 0
JCR@2023
CAS Journal Grade:4
Cited Count:
SCOPUS Cited Count:
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 0
Affiliated Colleges: