Academic Bibliography

 Search 200 years of publications by Ghent University researchers.
Advanced search
1 file | 394.65 KB
Add to list
  1. Search results
  2. Vertex degrees and 2-cuts in graphs w...

Vertex degrees and 2-cuts in graphs with many hamiltonian vertex-deleted subgraphs

Carol Zamfirescu (UGent)
(2022) INFORMATION PROCESSING LETTERS. 174.
Author
Organization
Project
Abstract
A 2-connected non-hamiltonian graph G is a k-graph if for exactly k < |V(G)| vertices in G, removing such a vertex yields a non-hamiltonian graph. We characterise k-graphs of connectivity 2 and describe structurally interesting examples of such graphs containing no cubic vertex or of minimum degree at least 4, with a special emphasis on the planar case. We prove that there exists a k_0 such that for every k \ge k_0 infinitely many planar k-graphs of connectivity 2 and minimum degree 4 exist. As a variation of a result of Thomassen, we show that certain planar 3-graphs must contain a cubic vertex.
Keywords
Computer Science Applications, Information Systems, Signal Processing, Theoretical Computer Science, Hamiltonian cycle, Planar graph, Hypohamiltonian, Combinatorial problems, CONSTRUCTIONS, PLANAR

Downloads

  • Download
    (...).pdf
    • full text (Published version)
    • |
    • UGent only
    • |
    • PDF
    • |
    • 394.65 KB

Citation

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

MLA
Zamfirescu, Carol. “Vertex Degrees and 2-Cuts in Graphs with Many Hamiltonian Vertex-Deleted Subgraphs.” INFORMATION PROCESSING LETTERS, vol. 174, 2022, doi:10.1016/j.ipl.2021.106192.
APA
Zamfirescu, C. (2022). Vertex degrees and 2-cuts in graphs with many hamiltonian vertex-deleted subgraphs. INFORMATION PROCESSING LETTERS, 174. https://doi.org/10.1016/j.ipl.2021.106192
Chicago author-date
Zamfirescu, Carol. 2022. “Vertex Degrees and 2-Cuts in Graphs with Many Hamiltonian Vertex-Deleted Subgraphs.” INFORMATION PROCESSING LETTERS 174. https://doi.org/10.1016/j.ipl.2021.106192.
Chicago author-date (all authors)
Zamfirescu, Carol. 2022. “Vertex Degrees and 2-Cuts in Graphs with Many Hamiltonian Vertex-Deleted Subgraphs.” INFORMATION PROCESSING LETTERS 174. doi:10.1016/j.ipl.2021.106192.
Vancouver
1.
Zamfirescu C. Vertex degrees and 2-cuts in graphs with many hamiltonian vertex-deleted subgraphs. INFORMATION PROCESSING LETTERS. 2022;174.
IEEE
[1]
C. Zamfirescu, “Vertex degrees and 2-cuts in graphs with many hamiltonian vertex-deleted subgraphs,” INFORMATION PROCESSING LETTERS, vol. 174, 2022.
@article{8740369,
  abstract     = {{A 2-connected non-hamiltonian graph G is a k-graph if for exactly k < |V(G)| vertices in G, removing such a vertex yields a non-hamiltonian graph. We characterise k-graphs of connectivity 2 and describe structurally interesting examples of such graphs containing no cubic vertex or of minimum degree at least 4, with a special emphasis on the planar case. We prove that there exists a k_0 such that for every k \ge k_0 infinitely many planar k-graphs of connectivity 2 and minimum degree 4 exist. As a variation of a result of Thomassen, we show that certain planar 3-graphs must contain a cubic vertex.}},
  articleno    = {{106192}},
  author       = {{Zamfirescu, Carol}},
  issn         = {{0020-0190}},
  journal      = {{INFORMATION PROCESSING LETTERS}},
  keywords     = {{Computer Science Applications,Information Systems,Signal Processing,Theoretical Computer Science,Hamiltonian cycle,Planar graph,Hypohamiltonian,Combinatorial problems,CONSTRUCTIONS,PLANAR}},
  language     = {{eng}},
  pages        = {{9}},
  title        = {{Vertex degrees and 2-cuts in graphs with many hamiltonian vertex-deleted subgraphs}},
  url          = {{http://doi.org/10.1016/j.ipl.2021.106192}},
  volume       = {{174}},
  year         = {{2022}},
}
Altmetric
View in Altmetric
Web of Science
Times cited: