کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
428481 | 686780 | 2016 | 6 صفحه PDF | دانلود رایگان |
• 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.
Journal: Information Processing Letters - Volume 116, Issue 5, May 2016, Pages 321–326