کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4652337 1632597 2009 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Ear decompositions of a cubic bridgeless graph and near P4-decompositions of its deck
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Ear decompositions of a cubic bridgeless graph and near P4-decompositions of its deck
چکیده انگلیسی

We show that when building an ear decomposition of a cubic bridgeless graph, it is possible to do this so that at each step, the graph outside the already built two-connected subgraph, has a 2-factor. It shall also be shown that every edge in a cubic bipartite graph is either a chord in some 2-factor or part of a 2-edge-cut. Furthermore every 3-regular bipartite graph has some 2-factor with a chord and if v is a vertex in a bipartite 3-regular graph B then B has a 2-factor F such that the component of F containing v has a chord at v, unless there exists a 2-vertex-cut {u,v} such that B−{u,v} has three components. We also show that if we let v be a vertex in a bridgeless cubic graph G, then G−v is the edge-disjoint union of paths of length 3 and at most one triangle. Finally let G be a 3-regular multigraph which can be made bipartite by the deletion of at most two edges, then G is 3-edge colourable.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 34, 1 August 2009, Pages 191-198