Linial’s Conjecture for Arc-spine Digraphs

dc.creatorRigo Yoshimura, Lucas
dc.creatorSambinelli, Maycon
dc.creatorNunes da Silva, Cândida
dc.creatorLee, Orlando
dc.date2019-06-17
dc.date.accessioned2022-10-04T23:27:08Z
dc.date.available2022-10-04T23:27:08Z
dc.identifierhttps://seer.ufrgs.br/index.php/reic/article/view/93601
dc.identifier.urihttp://repositorioslatinoamericanos.uchile.cl/handle/2250/3873496
dc.descriptionA 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-adjacentvertices 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.pt-BR
dc.formatapplication/pdf
dc.languagepor
dc.publisherRevista Eletrônica de Iniciação Científica em Computaçãopt-BR
dc.relationhttps://seer.ufrgs.br/index.php/reic/article/view/93601/53037
dc.rightsCopyright (c) 2019 Revista Eletrônica de Iniciação Científica em Computaçãopt-BR
dc.sourceRevista 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)pt-BR
dc.source1519-8219
dc.subjectdigraphspt-BR
dc.subjectpath partitionpt-BR
dc.subjectLinial's Conjecturept-BR
dc.titleLinial’s Conjecture for Arc-spine Digraphspt-BR
dc.typeinfo:eu-repo/semantics/article
dc.typeinfo:eu-repo/semantics/publishedVersion


Este ítem pertenece a la siguiente institución