Independent sets and non-augmentable paths in arc-locally in-semicomplete digraphs and quasi-arc-transitive digraphs

AbstractA digraph is arc-locally in-semicomplete if for any pair of adjacent vertices x,y, every in-neighbor of x and every in-neighbor of y either are adjacent or are the same vertex. A digraph is quasi-arc-transitive if for any arc xy, every in-neighbor of x and every out-neighbor of y either are adjacent or are the same vertex. Laborde, Payan and Xuong proposed the following conjecture: Every digraph has an independent set intersecting every non-augmentable path (in particular, every longest path). In this paper, we shall prove that this conjecture is true for arc-locally in-semicomplete digraphs and quasi-arc-transitive digraphs