Discussiones Mathematicae Graph Theory 33(2) (2013)
261-275

doi: 10.7151/dmgt.1650

Susan van Aardt, Marietjie Frick and Joy Singleton
Department of Mathematical Sciences |

**Keywords:** longest path, independent set, detour transversal, strong digraph, oriented graph

**2010 Mathematics Subject Classification:** 05C20, 05C38.

[1] | S.A. van Aardt, G. Dlamini, J. Dunbar, M. Frick, and O. Oellermann, The directed path partition conjecture, Discuss. Math. Graph Theory 25 (2005) 331--343, doi: 10.7151/dmgt.1286. |

[2] | S.A. van Aardt, J.E. Dunbar, M. Frick, P. Katrenič, M.H. Nielsen, and O.R. Oellermann, Traceability of , Discrete Math. k-traceable oriented graphs 310 (2010) 1325--1333, doi: 10.1016/j.disc.2009.12.022. |

[3] | J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications (Springer-Verlag, London, 2001). |

[4] | J. Bang-Jensen, M.H. Nielsen and A. Yeo, Longest path partitions in generalizations of tournaments, Discrete Math. 306 (2006) 1830--1839, doi: 10.1016/j.disc.2006.03.063. |

[5] | J.A. Bondy, Basic graph theory: Paths and circuits, in: Handbook of Combinatorics, ed(s), R.L. Graham, M. Grötschel and L. Lovász The MIT Press, Cambridge, MA, 1995) Vol I, p. 20. |

[6] | P. Camion, Chemins et circuits hamiltoniens des graphes complets, C.R. Acad. Sci. Paris 249 (1959) 2151--2152. |

[7] | C.C. Chen and P. Manalastas Jr., Every finite strongly connected digraph of stability , Discrete Math. 2 has a Hamiltonian path 44 (1983) 243--250, doi: 10.1016/0012-365X(83)90188-7. |

[8] | H. Galeana-Sánchez and R. Gómez, Independent sets and non-augmentable paths in generalizations of tournaments, Discrete Math. 308 (2008) 2460--2472, doi: 10.1016/j.disc.2007.05.016. |

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

[10] | F. Havet, Stable set meeting every longest path, Discrete Math. 289 (2004) 169--173, doi: 10.1016/j.disc.2004.07.013. |

[11] | J.M. Laborde, C. Payan, N.H. Xuong, Independent sets and longest directed paths in digraphs, in: Graphs and other combinatorial topics (Prague, 1982) 173--177 (Teubner-Texte Math., 59 1983). |

[12] | M. Richardson, Solutions of irreflexive relations, Ann. of Math. 58 (1953) 573--590, doi: 10.2307/1969755. |

Received 19 October 2011

Revised 28 February 2012

Accepted 28 February 2012