A family of counterexamples for a conjecture of Berge on αα-diperfect digraphs

preprint2022arXivOpen access

Abstract

Let DD be a digraph. A stable set SS of DD and a path partition P\mathcal{P} of DD are orthogonal if every path P∈PP \in \mathcal{P} contains exactly one vertex of SS. In 1982, Berge defined the class of αα-diperfect digraphs. A digraph DD is αα-diperfect if for every maximum stable set SS of DD there is a path partition P\mathcal{P} of DD orthogonal to SS and this property holds for every induced subdigraph of DD. An anti-directed odd cycle is an orientation of an odd cycle (x0,…,x2k,x0)(x_0,\ldots,x_{2k},x_0) with k≥2k\geq2 in which each vertex x0,x1,x2,x3,x5,x7…,x2k−1x_0,x_1,x_2,x_3,x_5,x_7\ldots,x_{2k-1} is either a source or a sink. Berge conjectured that a digraph DD is αα-diperfect if and only if DD 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 αα-diperfect.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.