Czasopismo
Tytuł artykułu
Autorzy
Treść / Zawartość
Pełne teksty:
Warianty tytułu
Języki publikacji
Abstrakty
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).
Słowa kluczowe
Kategorie tematyczne
Wydawca
Czasopismo
Rocznik
Tom
Numer
Strony
171-181
Opis fizyczny
Daty
wydano
1998
otrzymano
1998-01-16
poprawiono
1998-06-05
Twórcy
autor
- Instituto de Matemáticas, UNAM, Circuito Exterior, Ciudad Universitaria, 04510 México, D.F., México
Bibliografia
- [1] C. Berge, Graphs (North-Holland, 1985).
- [2] H. Galeana-Sánchez and H.A. Rincón-Mejía, Independent sets which meet all longest paths, Discrete Math. 152 (1996) 141-145, doi: 10.1016/0012-365X(94)00261-G.
- [3] P.A. Grillet, Maximal chains and antichains, Fund. Math. 65 (1969) 157-167.
- [4] J.M. Laborde, C. Payan and N.H. Huang, Independent sets and longest directed paths in digraphs, in: Graphs and Other Combinatorial Topics. Proceedings of the Third Czechoslovak Symposium of Graph Theory (1982) 173-177.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1073