| Full text | |
| Author(s): |
Freitas, Lucas Ismaily Bezerra
;
Lee, Orlando
Total Authors: 2
|
| Document type: | Journal article |
| Source: | GRAPHS AND COMBINATORICS; v. 38, n. 4, p. 23-pg., 2022-08-01. |
| Abstract | |
Let D be a digraph. A subset S of V(D) is stable if every pair of vertices in S is non-adjacent in D. A collection of disjoint paths P of D is a path partition of V(D), if every vertex in V(D) is on a path of P. We say that a stable set S and a path partition P are orthogonal if every path of P contains exactly one vertex of S. A digraph D satisfies the alpha-property if for every maximum stable set S of D, there is a path partition P orthogonal to S. A digraph D is alpha-diperfect if every induced subdigraph of D satisfies the alpha-property. In 1982, Berge proposed a characterization of alpha-diperfect digraphs in terms of forbidden anti-directed odd cycles. In 2018, Sambinelli, Silva and Lee proposed a similar conjecture. A digraph D satisfies the Begin-End-property or BE-property if for every maximum stable set S of D, there is a path partition P such that (i) S and P are orthogonal and (ii) for each path P is an element of P, either the initial or the final of P lies in S. A digraph D is BE-diperfect if every induced subdigraph of D satisfies the BE-property. Sambinelli, Silva and Lee proposed a characterization of BE-diperfect digraphs in terms of forbidden blocking odd cycles. In this paper, we show some structural results for alpha-diperfect and BE-diperfect digraphs. In particular, we show that in every minimal counterexample D to both conjectures, it follows that alpha(D)<vertical bar V(D)vertical bar/2. Moreover, we prove both conjectures for arc-locally (out) in-semicomplete digraphs. (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 |