Generalized Quasikernels in Digraphs
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914876025208832 |
|---|---|
| author | Spiro, Sam |
| author_facet | Spiro, Sam |
| contents | Given a digraph $D$, we say that a set of vertices $Q\subseteq 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]|\ge \frac{1}{2}|V(D)|$ for all $q\ge 2$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_07305 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Generalized Quasikernels in Digraphs Spiro, Sam Combinatorics 05C20, 05C35 Given a digraph $D$, we say that a set of vertices $Q\subseteq 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]|\ge \frac{1}{2}|V(D)|$ for all $q\ge 2$. |
| title | Generalized Quasikernels in Digraphs |
| topic | Combinatorics 05C20, 05C35 |
| url | https://arxiv.org/abs/2404.07305 |