A note on K4closures in Hamiltonian graph theory
Broersma, H.J. (1993) A note on K4closures in Hamiltonian graph theory. Discrete Mathematics, 121 (13). pp. 1923. ISSN 0012365X

PDF
317kB 
Abstract:  Let G=(V, E) be a 2connected graph. We call two vertices u and v of G a K4pair 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 K4pair u, v in an induced K4−e. We prove the following result: If N(x)N(y)N(u)N(v), then G is hamiltonian if and only if G+uv is h amiltonian. As a consequence, a clawfree graph G is hamiltonian if and only if G+uv is hamiltonian, where u,v is a K4pair. Based on these results we define socalled K4closures of G. We give infinite classes of graphs with small maximum degree and large diameter, and with many vertices of degree two having complete K4closures. 
Item Type:  Article 
Copyright:  © 1993 Elsevier Science 
Faculty:  Electrical Engineering, Mathematics and Computer Science (EEMCS) 
Research Group:  
Link to this item:  http://purl.utwente.nl/publications/29721 
Official URL:  http://dx.doi.org/10.1016/0012365X(93)90533Y 
Export this item as:  BibTeX EndNote HTML Citation Reference Manager 
Repository Staff Only: item control page
Metis ID: 140355