کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4647542 1342359 2013 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Circuit extension and circuit double cover of graphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Circuit extension and circuit double cover of graphs
چکیده انگلیسی

Let GG be a cubic graph and CC be a circuit. An extension of CC is a circuit DD such that V(C)⊆V(D)V(C)⊆V(D) and E(C)≠E(D)E(C)≠E(D). The study of circuit extension is motivated by the circuit double cover conjecture. It is proved by Fleischner (1990) that a circuit CC is extendable if CC has only one non-trivial Tutte bridge. It is further improved by Chan, Chudnovsky and Seymour (2009) that a circuit is extendable if it has only one odd Tutte bridge. Those earlier results are improved in this paper that CC is extendable if all odd Tutte bridges of CC are sequentially lined up along CC. It was proved that if every circuit is extendable for every bridgeless cubic graph, then the circuit double cover conjecture is true (Kahn, Robertson, Seymour 1987). Although graphs with stable circuits have been discovered by Fleischner (1994) and Kochol (2001), variations of this approach remain one of most promising approaches to the circuit double cover conjecture. Following some early investigation of Seymour and Fleischner, we further study the relation between circuit extension and circuit double cover conjecture, and propose a new approach to the conjecture. This new approach is verified for some graphs with stable circuits constructed by Fleischner and Kochol.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 313, Issue 20, 28 October 2013, Pages 2055–2060
نویسندگان
, , ,