# 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

| 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), 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