Longest cycles in threshold graphs

DOI10.1016/0012-365X(93)E0077-HMaRDI QIDQ1343260zbMATH OpenFDO

Authors N. V. R. Mahadev, Uri N. Peled

Publication date 1 February 1995

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(93)E0077-H

zbMATH Keywords

bipartite graphHamiltonian threshold graphslargest matchinglinear timelongest cyclethreshold graph

Mathematics Subject Classification ID

Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45) Structural characterization of families of graphs (05C75)

Recommendations

• Hamiltonian threshold graphs
• Notes on Hamiltonian threshold and chain graphs
• The minimum number of Hamilton cycles in a Hamiltonian threshold graph of a prescribed order
• Cycle spectra of Hamiltonian graphs
• Longest cycles in tough graphs

Cites work

• A Graph-Theoretic Characterization of the $\text{PV}_{\text{chunk}}$ Class of Synchronizing Primitives
• Enumeration of labelled threshold graphs and a theorem of Frobenius involving Eulerian polynomials
• Extreme degree sequences of simple graphs
• Graph theory
• Hamiltonian threshold graphs
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3710208 (Why is no real title available?)
• scientific article; zbMATH DE number 3743175 (Why is no real title available?)
• scientific article; zbMATH DE number 3561379 (Why is no real title available?)
• scientific article; zbMATH DE number 3598234 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• On Hamilton's ideals
• The polytope of degree sequences
• Threshold Sequences
• Trivially perfect graphs

Cited in

(6)

• On randomized stopping points and perfect graphs
• Hamiltonian powers in threshold and arborescent comparability graphs
• Notes on Hamiltonian threshold and chain graphs
• The longest cycle problem is polynomial on interval graphs
• Exact and approximate methods for the score-constrained packing problem
• On computing longest paths in small graph classes

This page was built for publication: Longest cycles in threshold graphs

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