ISSN 1234-3099 (print version)
ISSN 2083-5892 (electronic version)
SCImago Journal Rank (SJR) 2018: 0.763
Rejection Rate (2017-2018): c. 84%
Mathematicae Graph Theory 18(2) (1998) 171-181 DOI: 10.7151/dmgt.1073
Instituto de Matemáticas, UNAM
Circuito Exterior, Ciudad Universitaria
04510 México, D.F., México
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"
Keywords: digraph, independent set, directed path, non-augmentable path.
1991 Mathematics Subject Classification: 05C20.
Received 16 January 1998
Revised 5 June 1998