کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6423573 1342419 2011 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A sufficient condition for the existence of an anti-directed 2-factor in a directed graph
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
A sufficient condition for the existence of an anti-directed 2-factor in a directed graph
چکیده انگلیسی

Let D be a directed graph with vertex set V, arc set A, and order n. The graph underlying D is the graph obtained from D by replacing each arc (u,v)∈A by an undirected edge {u,v} and then replacing each double edge by a single edge. An anti-directed (hamiltonian) cycle H in D is a (hamiltonian) cycle in the graph underlying D such that no pair of consecutive arcs in H form a directed path in D. An anti-directed 2-factor in D is a vertex-disjoint collection of anti-directed cycles in D that span V. It was proved in Busch et al. (submitted for publication) [3] that if the indegree and the outdegree of each vertex of D is greater than 916n then D contains an anti-directed Hamilton cycle. In this paper we prove that given a directed graph D, the problem of determining whether D has an anti-directed 2-factor is NP-complete, and we use a proof technique similar to the one used in Busch et al. (submitted for publication) [3] to prove that if the indegree and the outdegree of each vertex of D is greater than 2446n then D contains an anti-directed 2-factor.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 311, Issue 21, 6 November 2011, Pages 2556-2562
نویسندگان
, , , ,