Article ID Journal Published Year Pages File Type
419245 Discrete Applied Mathematics 2016 9 Pages PDF
Abstract

Let PP be a graph property. A graph GG is said to be locally  PP if the subgraph induced by the open neighbourhood of every vertex in GG has property PP. Ryjáček’s well-known conjecture that every connected, locally connected graph is weakly pancyclic motivated us to consider the global cycle structure of locally PP graphs, where PP is, in turn, ‘connected’, ‘traceable’ and ‘hamiltonian’. We show that (i) the locally connected graphs with maximum degree at most 5 are all weakly pancyclic, but infinitely many are nonhamiltonian, (ii) all the connected, locally traceable graphs with maximum degree at most 5 are fully cycle extendable, except for three exceptional graphs, (iii) all the connected, locally hamiltonian graphs with maximum degree at most 6 are fully cycle extendable, (iv) if GG is a locally hamiltonian graph GG of order nn and maximum degree at least n−5n−5, then GG is weakly pancyclic.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , , ,