Hamiltonicity of regular graphs and blocks of consecutive ones in symmetric matrices

DOI10.1016/J.DAM.2007.06.009MaRDI QIDQ2457012zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 29 October 2007

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

Full work available at URL https://doi.org/10.1016/j.dam.2007.06.009

zbMATH Keywords

NP-completenessregular graphHamiltonicityconsecutive ones

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Eulerian and Hamiltonian graphs (05C45)

Recommendations

• On Hamiltonicity of regular graphs with bounded second neighborhoods
• Complexity of the hamiltonian cycle in regular graph problem
• Hamiltonian cycles in regular graphs of moderate degree
• Hamilton cycles in regular 3-connected graphs
• scientific article; zbMATH DE number 3966120

Cites work

• scientific article; zbMATH DE number 3652373 (Why is no real title available?)
• scientific article; zbMATH DE number 3679885 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1219584 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• Interval routing schemes
• Parallel concepts in graph theory
• Polynomial Complete Consecutive Information Retrieval Problems
• Structural Information and Communication Complexity
• The Compactness of Interval Routing
• The Planar Hamiltonian Circuit Problem is NP-Complete

Cited in

(11)

• A block negacyclic Bush-type Hadamard matrix and two strongly regular graphs
• The parameterized complexity of stabbing rectangles
• A new characterization of matrices with the consecutive ones property
• Cyclic arrangements with minimum modulo \(m\) winding numbers
• Linearity is strictly more powerful than contiguity for encoding graphs
• Linearity is strictly more powerful than contiguity for encoding graphs
• (Nearly-)tight bounds on the contiguity and linearity of cographs
• Obtaining matrices with the consecutive ones property by row deletions
• Blockers for simple Hamiltonian paths in convex geometric graphs of even order
• All-shortest-path 2-interval routing is NP-complete
• On the hardness of minimizing space for all-shortest-path interval routing schemes

This page was built for publication: Hamiltonicity of regular graphs and blocks of consecutive ones in symmetric matrices

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