2024/04/10 by Sam Spiro, Spiro, Sam · 1 citation
Computer Science · Mathematics · #05C20 #05C35 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2404.07305
openalex publication_date 2024/04/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
Given a digraph D, we say that a set of vertices Q⊆ V(D) is a q-kernel if Q is an independent set and if every vertex of D can be reached from Q by a path of length at most q. In this paper, we initiate the study of several extremal problems for q-kernels. For example, we introduce and make progress on (what turns out to be) a weak version of the Small Quasikernel Conjecture, namely that every digraph contains a q-kernel with |N+[Q]|≥ (1)/(2)|V(D)| for all q≥ 2.