کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4656673 1632973 2016 28 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Cycle covers (II) – Circuit chain, Petersen chain and Hamilton weights
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Cycle covers (II) – Circuit chain, Petersen chain and Hamilton weights
چکیده انگلیسی

The Circuit Double Cover Conjecture is one of the most challenging open problems in graph theory. The main result of the paper is related to the characterization of circuit chain structure, which has been one of the most popular approaches to the conjecture. Let G   be a bridgeless cubic graph associated with an eulerian weight w:E(G)→{1,2}w:E(G)→{1,2} such that (G,w)(G,w) does not have a faithful circuit cover. If, for every weight 2 edge e0e0 of (G,w)(G,w), the eulerian weighted graph (G−e0,w)(G−e0,w) has a faithful circuit cover and (G,w)(G,w) has no removable circuit avoiding e0e0, then it was proved (Alspach et al., 1993 [1] or 1994 [2]) that G contains a Petersen minor. It was further conjectured by Fleischner and Jackson (1988) that this graph G must be the Petersen graph. This conjecture was verified (JCTB 2010) recently under the assumption of the Hamilton weight conjecture. These two earlier results are further strengthened in this paper as follows. If, for a given weight 2 edge e0e0, the eulerian weighted graph (G−e0,w)(G−e0,w) has a faithful circuit cover and (G,w)(G,w) has no removable circuit avoiding e0e0, then, under the assumption of the Hamilton weight conjecture, G must be a Petersen chain. With a much weaker requirement “for a given  e0e0” instead of “for every  e0e0”, this strengthened result (structure of circuit chain joining a missing edge) is expected to be much more useful in future studies about circuit covering problems.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 120, September 2016, Pages 36–63
نویسندگان
,