Independent sets and non-augmentable paths in generalizations of tournaments |
| |
Authors: | Hortensia Galeana-Sá nchez |
| |
Affiliation: | Instituto de Matemáticas de la Universidad Nacional Autónoma de México, Área de la Investigación Científica. Circuito Exterior, Ciudad Universitaria, México D.F. 04510 México |
| |
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: | Independent set Non-augmentable path Longest path Generalization of tournament |
本文献已被 ScienceDirect 等数据库收录! |
|