Geodesic
On independent sets and non-augmentable paths in directed graphs
Discussiones Mathematicae. Graph Theory, Tome 18 (1998) no. 2, pp. 171-181 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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).
Keywords: digraph, independent set, directed path, non-augmentable path 
@article{DMGT_1998_18_2_a3,
     author = {Galeana-S\'anchez, H.},
     title = {On independent sets and non-augmentable paths in directed graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {171--181},
     year = {1998},
     volume = {18},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_1998_18_2_a3/}
}
TY  - JOUR
AU  - Galeana-Sánchez, H.
TI  - On independent sets and non-augmentable paths in directed graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 1998
SP  - 171
EP  - 181
VL  - 18
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DMGT_1998_18_2_a3/
LA  - en
ID  - DMGT_1998_18_2_a3
ER  - 
%0 Journal Article
%A Galeana-Sánchez, H.
%T On independent sets and non-augmentable paths in directed graphs
%J Discussiones Mathematicae. Graph Theory
%D 1998
%P 171-181
%V 18
%N 2
%U http://geodesic.mathdoc.fr/item/DMGT_1998_18_2_a3/
%G en
%F DMGT_1998_18_2_a3
Galeana-Sánchez, H. On independent sets and non-augmentable paths in directed graphs. Discussiones Mathematicae. Graph Theory, Tome 18 (1998) no. 2, pp. 171-181. http://geodesic.mathdoc.fr/item/DMGT_1998_18_2_a3/

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