Hamiltonian paths and cycles, number of arcs and independence number in digraphs

DOI10.1016/0012-365X(92)90139-7MaRDI QIDQ1199482zbMATH OpenOpenAlexFDO

Authors Y. Manoussakis, Denise Amar

Publication date 16 January 1993

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365x(92)90139-7

zbMATH Keywords

digraphsHamiltonian cyclesHamiltonian pathsindependence number

Mathematics Subject Classification ID

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

Review text

Let \(D\) denote a digraph with \(n\) vertices, at least \(\alpha\) independent vertices, and in which each vertex has in-degree and out-degree at least \(k\). The authors give bounds, in terms of \(n\) and \(\alpha\), and in terms of \(n\), \(\alpha\), and \(k\), on the number of arcs \(D\) can have without being Hamiltonian or Hamiltonian connected.

Recommendations

• scientific article; zbMATH DE number 3893232
• scientific article; zbMATH DE number 5931607
• A Chvátal-Erdős condition for Hamilton cycles in digraphs
• scientific article; zbMATH DE number 4066942
• scientific article; zbMATH DE number 4177106

Cites work

• Chemins Et Circuits Dans Les Graphes Orientes
• Cycles in digraphs– a survey
• scientific article; zbMATH DE number 4177106 (Why is no real title available?)
• scientific article; zbMATH DE number 3893232 (Why is no real title available?)
• On maximal circuits in directed graphs

Cited in

(5)

• A Chvátal-Erdős condition for Hamilton cycles in digraphs
• scientific article; zbMATH DE number 4066942 (Why is no real title available?)
• scientific article; zbMATH DE number 3893232 (Why is no real title available?)
• scientific article; zbMATH DE number 4198025 (Why is no real title available?)
• A note concerning paths and independence number in digraphs

This page was built for publication: Hamiltonian paths and cycles, number of arcs and independence number in digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1199482)