کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4650328 1342485 2008 14 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Contractible subgraphs, Thomassen’s conjecture and the dominating cycle conjecture for snarks
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Contractible subgraphs, Thomassen’s conjecture and the dominating cycle conjecture for snarks
چکیده انگلیسی

We show that the conjectures by Matthews and Sumner (every 4-connected claw-free graph is Hamiltonian), by Thomassen (every 4-connected line graph is Hamiltonian) and by Fleischner (every cyclically 4-edge-connected cubic graph has either a 3-edge-coloring or a dominating cycle), which are known to be equivalent, are equivalent to the statement that every snark (i.e. a cyclically 4-edge-connected cubic graph of girth at least five that is not 3-edge-colorable) has a dominating cycle.We use a refinement of the contractibility technique which was introduced by Ryjáček and Schelp in 2003 as a common generalization and strengthening of the reduction techniques by Catlin and Veldman and of the closure concept introduced by Ryjáček in 1997.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 308, Issue 24, 28 December 2008, Pages 6064–6077
نویسندگان
, , , , , ,