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.


Seen <100 times

More articles like this

A note on the minimum size of a vertex pancyclic g...

on Discrete Mathematics Jan 01, 1997

Vertex Pancyclic Graphs

on Electronic Notes in Discrete M... Jan 01, 1999

Vertex pancyclic graphs

on Discrete Applied Mathematics Jan 01, 2002
More articles like this..