DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 18(2) (1998) 171-181
DOI: 10.7151/dmgt.1073

ON INDEPENDENT SETS AND NON-AUGMENTABLE PATHS IN DIRECTED GRAPHS

H. Galeana-Sánchez

Instituto de Matemáticas, UNAM
Circuito Exterior, Ciudad Universitaria
04510 México, D.F., México

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

Keywords: digraph, independent set, directed path, non-augmentable path.

1991 Mathematics Subject Classification: 05C20.

References

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

Received 16 January 1998
Revised 5 June 1998