کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4654027 1632805 2011 15 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Orientable embeddings and orientable cycle double covers of projective-planar graphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Orientable embeddings and orientable cycle double covers of projective-planar graphs
چکیده انگلیسی

In a closed  22-cell embedding   of a graph each face is homeomorphic to an open disk and is bounded by a cycle in the graph. The Orientable Strong Embedding Conjecture says that every 22-connected graph has a closed 22-cell embedding in some orientable surface. This implies both the Cycle Double Cover Conjecture and the Strong Embedding Conjecture. In this paper we prove that every 22-connected projective-planar cubic graph has a closed 22-cell embedding in some orientable surface. The three main ingredients of the proof are (1) a surgical method to convert nonorientable embeddings into orientable embeddings; (2) a reduction for 44-cycles for orientable closed 22-cell embeddings, or orientable cycle double covers, of cubic graphs; and (3) a structural result for projective-planar embeddings of cubic graphs. We deduce that every 22-edge-connected projective-planar graph (not necessarily cubic) has an orientable cycle double cover.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Combinatorics - Volume 32, Issue 4, May 2011, Pages 495–509
نویسندگان
, ,