کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419245 | 683758 | 2016 | 9 صفحه PDF | دانلود رایگان |
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.
Journal: Discrete Applied Mathematics - Volume 205, 31 May 2016, Pages 171–179