Stable set meeting every longest path

DOI10.1016/j.disc.2004.07.013zbMath1056.05072OpenAlexW2015549411MaRDI QIDQ1763350

Frédéric Havet

Publication date: 22 February 2005

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2004.07.013

zbMATH Keywords

Stable setHamiltonian pathLongest path

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Eulerian and Hamiltonian graphs (05C45)

Related Items (7)

Computational results on the traceability of oriented graphs of small order ⋮ A linear bound towards the traceability conjecture ⋮ Independent sets and non-augmentable paths in generalizations of tournaments ⋮ Traceability of \(k\)-traceable oriented graphs ⋮ Longest path partitions in generalizations of tournaments ⋮ On a cycle partition problem ⋮ WHEN DO THREE LONGEST PATHS HAVE A COMMON VERTEX?

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Every finite strongly connected digraph of stability 2 has a Hamiltonian path
• A short proof of the Chen-Manalastas theorem
• Nombre chromatique et plus longs chemins d'un graphe

This page was built for publication: Stable set meeting every longest path