کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
428481 686780 2016 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Supereulerian digraphs with given local structures
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Supereulerian digraphs with given local structures
چکیده انگلیسی


• Jaeger-Catlin Theorem that every 4-edge-connected graph is supereulerian cannot be extended to digraphs.
• Catlin Theorem that every connected triangular graph is supereulerian cannot be extended to digraphs.
• There exist nontrivial digraph families such that if every arc of a strong digraph D lies in a member in the family, then D is supereulerian.

Catlin in 1988 indicated that there exist graph families FF such that if every edge e in a connected graph G   lies in a subgraph HeHe of G   isomorphic to a member in FF, then G is supereulerian. In particular, if every edge of a connected graph G lies in a 3-cycle, then G is supereulerian. The purpose of this research is to investigate how Catlin's theorem can be extended to digraphs. A strong digraph D is supereulerian if D   contains a spanning eulerian subdigraph. We show that there exists an infinite family of non-supereulerian strong digraphs each arc of which lies in a directed 3-cycle. We also show that there exist digraph families HH such that a strong digraph D is supereulerian if every arc a of D   lies in a subdigraph HaHa isomorphic to a member of HH. A digraph D   is symmetric if (x,y)∈A(D)(x,y)∈A(D) implies (y,x)∈A(D)(y,x)∈A(D); and is symmetrically connected if every pair of vertices of D are joined by a symmetric dipath. A digraph D is partially symmetric if the digraph obtained from D by contracting all symmetrically connected components is symmetrically connected. It is known that a partially symmetric digraph may not be symmetrically connected. We show that symmetrically connected digraphs and partially symmetric digraphs are such families. Sharpness of these results is discussed.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 116, Issue 5, May 2016, Pages 321–326
نویسندگان
, , , ,