- Tytuł:
- On independent sets and non-augmentable paths in directed graphs
- Autorzy:
- Galeana-Sánchez, H.
- Powiązania:
- https://bibliotekanauki.pl/articles/744219.pdf
- Data publikacji:
- 1998
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
digraph
independent set
directed path
non-augmentable path - Opis:
- We investigate sufficient conditions, and in case that D be an asymmetrical digraph a necessary and sufficient condition for a digraph to have the following property: "In any induced subdigraph H of D, every maximal independent set meets every non-augmentable path". Also we obtain a necessary and sufficient condition for any orientation of a graph G results a digraph with the above property. The property studied in this paper is an instance of the property of a conjecture of J.M. Laborde, Ch. Payan and N.H. Huang: "Every digraph contains an independent set which meets every longest directed path" (1982).
- Źródło:
-
Discussiones Mathematicae Graph Theory; 1998, 18, 2; 171-181
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł