The total interval number of a tree and the Hamiltonian completion number of its line graph

DOI10.1016/0020-0190(95)00163-8zbMath0875.68674OpenAlexW2055940060MaRDI QIDQ672831

Arundhati Raychaudhuri

Publication date: 28 February 1997

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(95)00163-8

zbMATH Keywords

Discrete mathematicsGraph theoryHamiltonian pathLine graphTreeCombinatorial problemsInterval graphHamiltonian completion numberTotal interval number

Mathematics Subject Classification ID

Combinatorics in computer science (68R05)

Related Items (10)

Total interval numbers of complete \(r\)-partite graphs ⋮ THE DEGREE PROFILE AND GINI INDEX OF RANDOM CATERPILLAR TREES ⋮ Evolutionary operators for the Hamiltonian completion problem ⋮ A lower bound on the Hamiltonian path completion number of a line graph ⋮ A linear algorithm for the Hamiltonian completion number of the line graph of a cactus. ⋮ Local search algorithms for finding the Hamiltonian completion number of line graphs ⋮ Hydras: complexity on general graphs and a subclass of trees ⋮ Hydras: directed hypergraphs and Horn formulas ⋮ Hamiltonian completions of sparse random graphs ⋮ A linear algorithm for the Hamiltonian completion number of the line graph of a tree

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The total interval number of a graph
• A linear algorithm for the Hamiltonian completion number of a tree
• On double and multiple interval graphs
• Extremal Values of the Interval Number of a Graph

This page was built for publication: The total interval number of a tree and the Hamiltonian completion number of its line graph