1
$\begingroup$

In graph theory, a Hamiltonian cycle is a cycle that visits each vertex exactly once. Hamiltonian cycle has a long history, and I have followed some articles.

We can find plenty of examples of Hamiltonian cycles by using google scholar.

  • S. Špacapan, A counterexample to prism-hamiltonicity of 3-connected planar graphs[J]. Journal of Combinatorial Theory, Series B, 2021, 146: 364-371.
  • Fabrici I, Harant J, Madaras T, et al. Long cycles and spanning subgraphs of locally maximal 1‐planar graphs[J]. Journal of Graph Theory, 2020, 95(1): 125-137.
  • Fabrici I, Madaras T, Timková M, et al. Non-hamiltonian graphs in which every edge-contracted subgraph is hamiltonian[J]. Applied Mathematics and Computation, 2021, 392: 125714.
  • Georges J P. Non-Hamiltonian bicubic graphs[J]. Journal of Combinatorial Theory, Series B, 1989, 46(1): 121-124. ...

But what I want to ask is：

  • Is there a monograph (or review) of Hamiltonian cycles of graphs (or long cycles of graphs)？

I've been looking for a long time, but I haven't seen some in-depth, systematic monographs. I know that there are monographs on graph coloring, matching, dominating set, crossing number, etc., respectively. There are even several books on some subjects, such as graph coloring or dominating set.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ I have not seen such a monograph either. You can ask these authors if there is a monograph on Hamiltonian cycles. 1) Gould, R. Advances on the Hamiltonian Problem – A Survey. Graphs and Combinatorics 19, 7–52 (2003); 2) Rahman, M. S., & Kaykobad, M. (2005). On Hamiltonian cycles and Hamiltonian paths. Information Processing Letters, 94(1), 37–41. doi:10.1016/j.ipl.2004.12.002 $\endgroup$
    – kabenyuk
    Nov 15, 2022 at 10:56
  • $\begingroup$ Ok, thanks. I will try to contact the authors by emails. These reviews are also great. I also just found a review of Hamiltonian problems on surfaces "K. Ozeki, Hamiltonicity of Graphs on Surfaces in Terms of Toughness and Scattering Number–A Survey[C]//Japanese Conference on Discrete and Computational Geometry, Graphs, and Games. Springer, Cham, 2018: 74-95.". To my surprise, I haven't seen a systematic monograph so far. I don't know what the difficulty is compared to other topics like coloring. $\endgroup$
    – L.C. Zhang
    Nov 15, 2022 at 11:27

1 Answer 1

Reset to default
2
$\begingroup$

Q: Is there a monograph (or review) of Hamiltonian cycles of graphs (or long cycles of graphs)？

One possible answer (from a specific perspective) is

Hamiltonian Cycle Problem and Markov Chains (2012)

This monograph summarizes a line of research that casts the Hamiltonian Cycle Problem in a mathematical framework which permits analytical concepts and techniques to clarify both the underlying difficulty of the NP-completeness of this problem and the relative exceptionality of truly difficult instances. The material is arranged in such a manner that the introductory chapters require very little mathematical background and discuss instances of graphs with interesting structures that motivated a lot of the research in this topic.

Improve this answer
$\endgroup$
1
  • $\begingroup$ It's a great book written from a certain point of view. But it's still far from the distance I want. I prefer the structural aspect of the graph itself. $\endgroup$
    – L.C. Zhang
    Nov 16, 2022 at 2:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.