کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4650291 1342483 2007 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Even subgraphs of bridgeless graphs and 2-factors of line graphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Even subgraphs of bridgeless graphs and 2-factors of line graphs
چکیده انگلیسی

By Petersen's theorem, a bridgeless cubic multigraph has a 2-factor. Fleischner generalised this result to bridgeless multigraphs of minimum degree at least three by showing that every such multigraph has a spanning even subgraph. Our main result is that every bridgeless simple graph with minimum degree at least three has a spanning even subgraph in which every component has at least four vertices. We deduce that if G is a simple bridgeless graph with n   vertices and minimum degree at least three, then its line graph has a 2-factor with at most max{1,(3n-4)/10}max{1,(3n-4)/10} components. This upper bound is best possible.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 307, Issue 22, 28 October 2007, Pages 2775–2785
نویسندگان
, ,