A sufficient condition for the existence of an anti-directed 2-factor in a directed graph

DOI10.1016/J.DISC.2011.07.033zbMATH Open1238.05209arXiv1012.1231OpenAlexW2014769093MaRDI QIDQ409370FDOQ409370

Authors: Ajit A. Diwan, Josh B. Frye, Michael J. Plantholt, Shailesh K. Tipnis 

Publication date: 13 April 2012

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: Let D be a directed graph with vertex set V and order n. 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 [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 [3] to prove that if the indegree and the outdegree of each vertex of D is greater than (24/46)n then D contains an anti-directed 2-factor.

Full work available at URL: https://arxiv.org/abs/1012.1231

Recommendations

• Improved sufficient conditions for the existence of anti-directed Hamiltonian cycles in digraphs
• Semi-degree threshold for anti-directed Hamiltonian cycles
• Vertex-oriented Hamilton cycles in directed graphs
• On the Dirac-type conjecture for anti-directed Hamiltonian digraphs
• The directed anti-Oberwolfach solution: Pancyclic 2-factorizations of complete directed graphs of odd order

zbMATH Keywords

directed graph2-factoranti-directed

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Graph theory
• On Hamilton's ideals
• Some Theorems on Abstract Graphs
• Digraphs. Theory, algorithms and applications
• Parallel concepts in graph theory
• Title not available (Why is that?)
• A counterexample to a conjecture of Grant
• Improved sufficient conditions for the existence of anti-directed Hamiltonian cycles in digraphs
• Title not available (Why is that?)
• Studies on directed graphs. I, II

Cited In (2)

• Improved sufficient conditions for the existence of anti-directed Hamiltonian cycles in digraphs
• Semi-degree threshold for anti-directed Hamiltonian cycles

This page was built for publication: A sufficient condition for the existence of an anti-directed 2-factor in a directed graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q409370)