Autor(es)

Silva, Caroline Aparecida de Paula ; da Silva, Candida Nunes ; Lee, Orlando

• Tipo de documento: Artigo Científico
• Fonte: DISCRETE MATHEMATICS; v. 346, n. 8, p. 6-pg., 2023-04-19.

Resumo

Let D be a digraph. A stable set S of D and a path partition P of D are orthogonal if every path P is an element of P contains exactly one vertex of S. In 1982, Berge defined the class of alpha-diperfect digraphs. A digraph D is alpha-diperfect if for every maximum stable set S of D there is a path partition P of D orthogonal to S and this property holds for every induced subdigraph of D. An anti-directed odd cycle is an orientation of an odd cycle (x0, . . . , x2k, x0) with k >= 2 in which each vertex x0, x1, x2, x3, x5, x7, ... , x2k-1 is either a source or a sink. Berge conjectured that a digraph D is alpha-diperfect if and only if D does not contain an anti -directed odd cycle as an induced subdigraph. In this paper, we show that this conjecture is false by exhibiting an infinite family of orientations of complements of odd cycles with at least seven vertices that are not alpha-diperfect. (c) 2023 Elsevier B.V. All rights reserved. (AU)

• Processo FAPESP: 20/06116-4 - Dígrafos chi-Diperfeitos
• Beneficiário: Caroline Aparecida de Paula Silva
• Modalidade de apoio: Bolsas no Brasil - Mestrado
• Processo FAPESP: 15/11937-9 - Investigação de problemas difíceis do ponto de vista algorítmico e estrutural
• Beneficiário: Flávio Keidi Miyazawa
• Modalidade de apoio: Auxílio à Pesquisa - Temático