Linial's Conjecture for Arc-spine Digraphs
| Autor: | Lucas Rigo Yoshimura, Orlando Lee, Maycon Sambinelli, Cândida Nunes da Silva |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Conjecture
General Computer Science 020207 software engineering Digraph 0102 computer and information sciences 02 engineering and technology Disjoint sets 01 natural sciences Theoretical Computer Science Vertex (geometry) Combinatorics Computer Science::Discrete Mathematics 010201 computation theory & mathematics Independent set 0202 electrical engineering electronic engineering information engineering Partition (number theory) Mathematics |
| Zdroj: | LAGOS |
| ISSN: | 1571-0661 |
| DOI: | 10.1016/j.entcs.2019.08.064 |
| Popis: | 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 ∑ P ∈ 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 vertices of V(D). Given a positive integer k, we denote by α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 πk(D) ≤ α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: |
|
Full Text from ScienceDirect