A note on K4-closures in Hamiltonian graph theory


Broersma, H.J. (1993) A note on K4-closures in Hamiltonian graph theory. Discrete Mathematics, 121 (1-3). pp. 19-23. ISSN 0012-365X

open access
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.
Item Type:Article
Copyright:© 1993 Elsevier Science
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/29721
Official URL:https://doi.org/10.1016/0012-365X(93)90533-Y
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page

Metis ID: 140355