Advanced search
1 file | 115.34 KB Add to list

Every 4-connected graph with crossing number 2 is Hamiltonian

Author
Organization
Abstract
A seminal theorem of Tutte states that 4-connected planar graphs are Hamiltonian. Applying a result of Thomas and Yu, one can show that every 4-connected graph with crossing number 1 is Hamiltonian. In this paper, we continue along this path and prove the titular statement. We also discuss the traceability and Hamiltonicity of 3-connected graphs with small crossing number and few 3-cuts, and present applications of our results.
Keywords
Hamiltonian cycle, crossing number, 3-cuts, PLANAR, PATHS, CYCLES

Downloads

  • oz-cross 2018 0919.pdf
    • full text
    • |
    • open access
    • |
    • PDF
    • |
    • 115.34 KB

Citation

Please use this url to cite or link to this publication:

MLA
Ozeki, Kenta, and Carol Zamfirescu. “Every 4-connected Graph with Crossing Number 2 Is Hamiltonian.” SIAM JOURNAL ON DISCRETE MATHEMATICS 32.4 (2018): 2783–2794. Print.
APA
Ozeki, K., & Zamfirescu, C. (2018). Every 4-connected graph with crossing number 2 is Hamiltonian. SIAM JOURNAL ON DISCRETE MATHEMATICS, 32(4), 2783–2794.
Chicago author-date
Ozeki, Kenta, and Carol Zamfirescu. 2018. “Every 4-connected Graph with Crossing Number 2 Is Hamiltonian.” Siam Journal on Discrete Mathematics 32 (4): 2783–2794.
Chicago author-date (all authors)
Ozeki, Kenta, and Carol Zamfirescu. 2018. “Every 4-connected Graph with Crossing Number 2 Is Hamiltonian.” Siam Journal on Discrete Mathematics 32 (4): 2783–2794.
Vancouver
1.
Ozeki K, Zamfirescu C. Every 4-connected graph with crossing number 2 is Hamiltonian. SIAM JOURNAL ON DISCRETE MATHEMATICS. 2018;32(4):2783–94.
IEEE
[1]
K. Ozeki and C. Zamfirescu, “Every 4-connected graph with crossing number 2 is Hamiltonian,” SIAM JOURNAL ON DISCRETE MATHEMATICS, vol. 32, no. 4, pp. 2783–2794, 2018.
@article{8585100,
  abstract     = {A seminal theorem of Tutte states that 4-connected planar graphs are Hamiltonian. Applying a result of Thomas and Yu, one can show that every 4-connected graph with crossing number 1 is Hamiltonian. In this paper, we continue along this path and prove the titular statement. We also discuss the traceability and Hamiltonicity of 3-connected graphs with small crossing number and few 3-cuts, and present applications of our results.},
  author       = {Ozeki, Kenta and Zamfirescu, Carol},
  issn         = {0895-4801},
  journal      = {SIAM JOURNAL ON DISCRETE MATHEMATICS},
  keywords     = {Hamiltonian cycle,crossing number,3-cuts,PLANAR,PATHS,CYCLES},
  language     = {eng},
  number       = {4},
  pages        = {2783--2794},
  title        = {Every 4-connected graph with crossing number 2 is Hamiltonian},
  url          = {http://dx.doi.org/10.1137/17m1138443},
  volume       = {32},
  year         = {2018},
}

Altmetric
View in Altmetric
Web of Science
Times cited: