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

DOI10.1016/J.DAM.2007.06.009zbMATH Open1125.05066OpenAlexW2121584049MaRDI QIDQ2457012FDOQ2457012

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

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

zbMATH Keywords

NP-completenessregular graphHamiltonicityconsecutive ones

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• The Planar Hamiltonian Circuit Problem is NP-Complete
• Title not available (Why is that?)
• Title not available (Why is that?)
• Parallel concepts in graph theory
• The Compactness of Interval Routing
• Interval routing schemes
• Polynomial Complete Consecutive Information Retrieval Problems
• Title not available (Why is that?)
• Structural Information and Communication Complexity

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)