Home About Upload Latest Additions Statistics Contact
UT Proceedings
UT Student Theses
Dutch Academic Output Dutch Dissertations EU Publications (OpenAIRE)
Printversion
Advanced search

A note on K4-closures in Hamiltonian graph theory

Share/Save/Bookmark

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

[img]
Preview
PDF
309Kb
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
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/0012-365X(93)90533-Y
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page

Metis ID: 140355