PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
1998 | 18 | 2 | 171-181
Tytuł artykułu

On independent sets and non-augmentable paths in directed graphs

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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).
Wydawca
Rocznik
Tom
18
Numer
2
Strony
171-181
Opis fizyczny
Daty
wydano
1998
otrzymano
1998-01-16
poprawiono
1998-06-05
Twórcy
  • 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
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.