Longest cycles in threshold graphs

DOI10.1016/0012-365X(93)E0077-HzbMath0810.05045MaRDI QIDQ1343260

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

Publication date: 1 February 1995

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

zbMATH Keywords

bipartite graphlinear timelongest cyclethreshold graphlargest matchingHamiltonian threshold graphs

Mathematics Subject Classification ID

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

Related Items (5)

On randomized stopping points and perfect graphs ⋮ Exact and approximate methods for the score-constrained packing problem ⋮ The longest cycle problem is polynomial on interval graphs ⋮ ON COMPUTING LONGEST PATHS IN SMALL GRAPH CLASSES ⋮ Hamiltonian powers in threshold and arborescent comparability graphs

Cites Work

• The polytope of degree sequences
• Hamiltonian threshold graphs
• Enumeration of labelled threshold graphs and a theorem of Frobenius involving Eulerian polynomials
• Trivially perfect graphs
• On Hamilton's ideals
• Extreme degree sequences of simple graphs
• Threshold Sequences
• A Graph-Theoretic Characterization of the $\text{PV}_{\text{chunk}}$ Class of Synchronizing Primitives
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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