Quasi-kernels in split graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866911783503003648 |
|---|---|
| author | Langlois, Hélène Meunier, Frédéric Rizzi, Romeo Vialette, Stéphane Zhou, Yacong |
| author_facet | Langlois, Hélène Meunier, Frédéric Rizzi, Romeo Vialette, Stéphane Zhou, Yacong |
| contents | In a digraph, a quasi-kernel is a subset of vertices that is independent and such that the shortest path from every vertex to this subset is of length at most two. The ``small quasi-kernel conjecture,'' proposed by Erdős and Székely in 1976, postulates that every sink-free digraph has a quasi-kernel whose size is within a fraction of the total number of vertices. The conjecture is even more precise with a $1/2$ ratio, but even with larger ratio, this property is known to hold only for few classes of graphs. The focus here is on small quasi-kernels in split graphs. This family of graphs has played a special role in the study of the conjecture since it was used to disprove a strengthening that postulated the existence of two disjoint quasi-kernels. The paper proves that every sink-free split digraph $D$ has a quasi-kernel of size at most $\frac{2}{3}|V(D)|$, and even of size at most two when the graph is an orientation of a complete split graph. It is also shown that computing a quasi-kernel of minimal size in a split digraph is W[2]-hard. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_15519 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Quasi-kernels in split graphs Langlois, Hélène Meunier, Frédéric Rizzi, Romeo Vialette, Stéphane Zhou, Yacong Combinatorics Discrete Mathematics 05C69 G.2.2 In a digraph, a quasi-kernel is a subset of vertices that is independent and such that the shortest path from every vertex to this subset is of length at most two. The ``small quasi-kernel conjecture,'' proposed by Erdős and Székely in 1976, postulates that every sink-free digraph has a quasi-kernel whose size is within a fraction of the total number of vertices. The conjecture is even more precise with a $1/2$ ratio, but even with larger ratio, this property is known to hold only for few classes of graphs. The focus here is on small quasi-kernels in split graphs. This family of graphs has played a special role in the study of the conjecture since it was used to disprove a strengthening that postulated the existence of two disjoint quasi-kernels. The paper proves that every sink-free split digraph $D$ has a quasi-kernel of size at most $\frac{2}{3}|V(D)|$, and even of size at most two when the graph is an orientation of a complete split graph. It is also shown that computing a quasi-kernel of minimal size in a split digraph is W[2]-hard. |
| title | Quasi-kernels in split graphs |
| topic | Combinatorics Discrete Mathematics 05C69 G.2.2 |
| url | https://arxiv.org/abs/2312.15519 |