A note on K4-closures in Hamiltonian graph theory

Research output: Contribution to journalArticleAcademicpeer-review

9 Citations (Scopus)
805 Downloads (Pure)

Abstract

Let G=(V, E) be a 2-connected graph. We call two vertices u and v of G a K4-pair if u and v are the vertices of degree two of an induced subgraph of G which is isomorphic to K4 minus an edge. Let x and y be the common neighbors of a K4-pair u, v in an induced K4−e. We prove the following result: If N(x)N(y)N(u)N(v){u,v}, then G is hamiltonian if and only if G+uv is h amiltonian. As a consequence, a claw-free graph G is hamiltonian if and only if G+uv is hamiltonian, where u,v is a K4-pair. Based on these results we define socalled K4-closures of G. We give infinite classes of graphs with small maximum degree and large diameter, and with many vertices of degree two having complete K4-closures.
Original languageEnglish
Pages (from-to)19-23
Number of pages5
JournalDiscrete mathematics
Volume121
Issue number121
DOIs
Publication statusPublished - 1993

Keywords

  • IR-29721
  • METIS-140355

Fingerprint Dive into the research topics of 'A note on K4-closures in Hamiltonian graph theory'. Together they form a unique fingerprint.

Cite this