TY - JOUR
AU - Rigo Yoshimura, Lucas
AU - Sambinelli, Maycon
AU - Nunes da Silva, Cândida
AU - Lee, Orlando
PY - 2019/06/17
Y2 - 2021/04/12
TI - Linial’s Conjecture for Arc-spine Digraphs
JF - Revista Eletrônica de Iniciação Científica em Computação
JA - REIC
VL - 17
IS - 2
SE - Edição Especial: CTIC/CSBC
DO - 10.5753/reic.2019.1090
UR - https://sol.sbc.org.br/journals/index.php/reic/article/view/1090
SP -
AB - <p>A path partition 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 P of D is defined as Sum (p in P) min{|p_i|, k}. A path partition of a minimum k-norm is called k-optimal and its k-norm is denoted by π_k(D). A stable set of a digraph D is a subset of pairwise non-adjacent<br />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) ≤ 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.</p>
ER -