alpha-Diperfect digraphs

Author(s)

Sambinelli, M. ; Nunes da Silva, C. ; Lee, O.

• Document type: Journal article
• Source: DISCRETE MATHEMATICS; v. 345, n. 5, p. 12-pg., 2022-05-01.

Abstract

Let D be a digraph. Given a set of vertices S subset of V (D), an S-path partition P of D is a collection of paths of D such that {V(P): P is an element of P} is a partition of V (D) and |V (P) boolean AND S| =1 for every P is an element of P. We say that D satisfies the alpha-property if, for every maximum stable set S of D, there exists an S-path partition of D, and we say that D is alpha-diperfect if every induced subdigraph of D satisfies the alpha-property. A digraph C is an anti-directed odd cycle if (i) the underlying graph of C is a cycle x(1)x(2) . . .x(2k+1)x(1), where k is an element of Z and k >= 2, and (ii) each of the vertices x(1), x(2), x(3), x(4), x(6), x(8), . . . , x(2k) is either a source or a sink. Berge (1982) conjectured that a digraph is alpha-diperfect if and only if it contains no induced anti-directed odd cycle. In this paper, we verify this conjecture for digraphs whose underlying graphs are series-parallel and for in-semicomplete digraphs. Moreover, we propose a conjecture similar to Berge's and verify it for the same classes. (c) 2022 Elsevier B.V. All rights reserved. (AU)

• FAPESP's process: 15/11937-9 - Investigation of hard problems from the algorithmic and structural stand points
• Grantee: Flávio Keidi Miyazawa
• Support Opportunities: Research Projects - Thematic Grants
• FAPESP's process: 17/23623-4 - Partition problems in graphs and digraphs
• Grantee: Maycon Sambinelli
• Support Opportunities: Scholarships in Brazil - Post-Doctoral