# On independent sets and non-augmentable paths in directed graphs

Discussiones Mathematicae Graph Theory (1998)

- Volume: 18, Issue: 2, page 171-181
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topH. Galeana-Sánchez. "On independent sets and non-augmentable paths in directed graphs." Discussiones Mathematicae Graph Theory 18.2 (1998): 171-181. <http://eudml.org/doc/270216>.

@article{H1998,

abstract = {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).},

author = {H. Galeana-Sánchez},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {digraph; independent set; directed path; non-augmentable path; maximal independent set},

language = {eng},

number = {2},

pages = {171-181},

title = {On independent sets and non-augmentable paths in directed graphs},

url = {http://eudml.org/doc/270216},

volume = {18},

year = {1998},

}

TY - JOUR

AU - H. Galeana-Sánchez

TI - On independent sets and non-augmentable paths in directed graphs

JO - Discussiones Mathematicae Graph Theory

PY - 1998

VL - 18

IS - 2

SP - 171

EP - 181

AB - 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).

LA - eng

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

UR - http://eudml.org/doc/270216

ER -

## References

top- [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. Zbl0191.00601
- [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.

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.