A sufficient condition for the existence of an anti-directed 2-factor in a directed graph
DSpace at IIT Bombay
View Archive InfoField | Value | |
Title |
A sufficient condition for the existence of an anti-directed 2-factor in a directed graph
|
|
Creator |
DIWAN, AA
FRYE, JB PLANTHOLT, MJ TIPNIS, SK |
|
Subject |
Anti-directed
2-factor Directed graph |
|
Description |
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) is an element of A by an undirected edge {u. v} land 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 9/16 n 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 24/46n then D contains an anti-directed 2-factor. (C) 2011 Elsevier B.V. All rights reserved.
|
|
Publisher |
ELSEVIER SCIENCE BV
|
|
Date |
2012-06-26T06:36:52Z
2012-06-26T06:36:52Z 2011 |
|
Type |
Article
|
|
Identifier |
DISCRETE MATHEMATICS,311(21)2556-2562
0012-365X http://dx.doi.org/10.1016/j.disc.2011.07.033 http://dspace.library.iitb.ac.in/jspui/handle/100/14054 |
|
Language |
English
|
|