Notes on Hamiltonian threshold and chain graphs

DOI10.3934/MATH.2021300MaRDI QIDQ2133251zbMATH OpenOpenAlexFDO

Authors Milica Andelić, Tamara Koledin, Zoran Stanić

Publication date 29 April 2022

Published in AIMS Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2005.09566

zbMATH Keywords

algorithmbinary sequencechain graphHamiltonian graphthreshold graph

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45)

Abstract: We revisit results obtained in [F. Harary, U. Peled, Hamiltonian threshold graphs, Discrete Appl.~Math., 16 (1987), 11--15], where several necessary and necessary and sufficient conditions for a connected threshold graph to be Hamiltonian were obtained. We present these results in new forms, now stated in terms of structural parameters that uniquely define the threshold graph and we extend them to chain graphs. We also identify the chain graph with minimum number of Hamilton cycles within the class of Hamiltonian chain graphs of a given order.

Recommendations

• Hamiltonian threshold graphs
• The minimum number of Hamilton cycles in a Hamiltonian threshold graph of a prescribed order
• Longest cycles in threshold graphs
• Hamiltonian powers in threshold and arborescent comparability graphs
• scientific article; zbMATH DE number 1205987

Cites work

• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Hamiltonian threshold graphs
• Laplacian controllability for graphs with integral Laplacian spectrum
• On Hamiltonian bipartite graphs
• The minimum number of Hamilton cycles in a Hamiltonian threshold graph of a prescribed order
• Threshold graphs and related topics

Cited in

(6)

• Hamiltonian threshold graphs
• Longest cycles in threshold graphs
• A short note on graphs with long Thomason chains
• Some Properties of Chain and Threshold Graphs
• On the eccentricity spectra of chain graphs
• Hamiltonian path in permutation graphs

This page was built for publication: Notes on Hamiltonian threshold and chain graphs

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