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).
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1073,
author = {H. Galeana-S\'anchez},
title = {On independent sets and non-augmentable paths in directed graphs},
journal = {Discussiones Mathematicae Graph Theory},
volume = {18},
year = {1998},
pages = {171-181},
zbl = {0926.05020},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1073}
}
H. Galeana-Sánchez. On independent sets and non-augmentable paths in directed graphs. Discussiones Mathematicae Graph Theory, Tome 18 (1998) pp. 171-181. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1073/
[000] [1] C. Berge, Graphs (North-Holland, 1985).
[001] [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.
[002] [3] P.A. Grillet, Maximal chains and antichains, Fund. Math. 65 (1969) 157-167. | Zbl 0191.00601
[003] [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.