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
topHow 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 ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.