کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
419245 683758 2016 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Global cycle properties in locally connected, locally traceable and locally hamiltonian graphs
ترجمه فارسی عنوان
خواص چرخه جهانی در نمودارهای همیلتون محلی، پیوسته و به صورت محلی قابل ردیابی
کلمات کلیدی
محلی متصل شده؛ به صورت محلی قابل ردیابی؛ هامیلتونی محلی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 205, 31 May 2016, Pages 171–179
نویسندگان
, , , ,