Affordable Access

A note on the minimum size of a vertex pancyclic graph

Publication Date
  • Mathematics


PII: 0012-365X(93)90533-Y Discrete Mathematics 121 (1993) 19-23 North-Holland I9 A note on &-closures in hamiltonian graph theory H. J. Broersma Department of’ Applied Nether1and.s Received I5 November Revised 24 April 1991 Abstract 1990 Broersma, H.J., A note on K,-closures in hamiltonian graph theory, Discrete Mathematics 121 (1993) 19-23. Let G =( V, E) be a 2-connected graph. We call two vertices u and c of G a K?-pair if u and L’ are the vertices of degree two of an induced subgraph of G which is isomorphic to K, minus an edge. Let x and y be the common neighbors of a K,-pair u, c in an induced K,-e. We prove the following result: If N(x)uN(y)~N(u)uN(v)uju, c}, then G is hamiltonian if and only if Gfuc is hamiltonian. As a consequence, a claw-free graph G is hamiltonian if and only if G + UC is hamiltonian, where u, L’ is a K,-pair. Based on these results we define socalled K,-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 K,-closures. 1. Introduction We use Bondy and Murty [4] for terminology and notation not defined here and consider simple graphs only. About 15 years ago the now well-known paper ‘A method in graph theory’ by Bondy and Chvhtal [3] was published. The closure concept they introduced in this paper opened a new horizon for the research on hamiltonian and related properties. We focus on the hamiltonian problem and mention their main results. In the sequel let G be a graph on n vertices, and let d(x) denote the degree of the vertex x of G. Lemma 1 [3]. Let u and G’ be distinct nonadjacent vertices in G such that d(u) + d(v) 3 n. Then G is hamiltonian if and only if G + uv is hamiltonian. Correspondence to: H.J. Broersma, Department of Applied Mathematics, University of Twente, P.O. Box 217, 7500 AE Enschede, Netherlands. 0012-365X/93/$06.00 C) 1993- -Elsevier Science Publishers B.V. All rights reserve

There are no comments yet on this publication. Be the first to share your thoughts.