On independent sets and non-augmentable paths in directed graphs

• Autorzy: H. Galeana-Sánchez
• 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).

Słowa kluczowe

EN

digraph; independent set; directed path; non-augmentable path

Kategorie tematyczne

• 05C20: Directed graphs (digraphs), tournaments

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 1998
• Tom: 18
• Numer: 2
• Strony: 171-181

Daty

wydano

1998

otrzymano

1998-01-16

poprawiono

1998-06-05

Twórcy

autor

H. Galeana-Sánchez

• 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.

Identyfikatory

DOI

10.7151/dmgt.1073