Linial’s Conjecture for Arc-spine Digraphs
| Autor: | Orlando Lee, Maycon Sambinelli, Lucas Rigo Yoshimura, Cândida Nunes da Silva |
|---|---|
| Přispěvatelé: | FAPESP |
| Jazyk: | portugalština |
| Rok vydání: | 2019 |
| Předmět: |
Combinatorics
Conjecture Computer Science::Discrete Mathematics Independent set Partition (number theory) Digraph General Medicine Disjoint sets digraphs path partition Linial's Conjecture Computer Science::Data Structures and Algorithms Mathematics Vertex (geometry) Algoritmos e Teoria da Computação Teoria dos Grafos |
| Zdroj: | Revista Eletrônica de Iniciação Científica em Computação; v. 17, n. 2 (2019): Edição Especial: Artigos do 38º Concurso de Trabalhos de Iniciação Científica (CSBC/CTIC) |
| ISSN: | 1519-8219 |
| Popis: | A \emph{path partition} $\mathcal{P}$ of a digraph $D$ is a collection of directed paths such that every vertex belongs to precisely one path. Given a positive integer $k$, the $k$-norm of a path partition $\mathcal{P}$ of $D$ is defined as $\sum_{P \in \mathcal{P}} \min\{|P_i|, k\}$. A path partition of a minimum $k$-norm is called $k$-optimal and its $k$-norm is denoted by $\pi_k(D)$. A \emph{stable set} of a digraph $D$ is a subset of pairwise non-adjacent vertices of $V(D)$. Given a positive integer $k$, we denote by $\alpha_k(D)$ the largest set of vertices of $D$ that can be decomposed into $k$ disjoint stable sets of $D$. In 1981, Linial conjectured that $\pi_k(D) \leq \alpha_k(D)$ for every digraph. We say that a digraph $D$ is arc-spine if $V(D)$ can be partitioned into two sets $X$ and $Y$ where $X$ is traceable and $Y$ contains at most one arc in $A(D)$. In this paper we show the validity of Linial's Conjecture for arc-spine digraphs. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|