Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4650680 | Discrete Mathematics | 2008 | 13 Pages |
Abstract
We study different classes of digraphs, which are generalizations of tournaments, to have the property of possessing a maximal independent set intersecting every non-augmentable path (in particular, every longest path). The classes are the arc-local tournament, quasi-transitive, locally in-semicomplete (out-semicomplete), and semicomplete k-partite digraphs. We present results on strongly internally and finally non-augmentable paths as well as a result that relates the degree of vertices and the length of longest paths. A short survey is included in the introduction.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Hortensia Galeana-Sánchez, Ricardo Gómez,