Vertex-oriented Hamilton cycles in directed graphs

Michael J. Plantholt ; Shailesh K. Tipnis

The electronic journal of combinatorics, Tome 16 (2009) no. 1

Résumé

Let $D$ be a directed graph of order $n$. An anti-directed Hamilton cycle $H$ in $D$ is a Hamilton cycle in the graph underlying $D$ such that no pair of consecutive arcs in $H$ form a directed path in $D$. We prove that if $D$ is a directed graph with even order $n$ and if the indegree and the outdegree of each vertex of $D$ is at least ${2\over 3}n$ then $D$ contains an anti-directed Hamilton cycle. This improves a bound of Grant. Let $V(D) = P \cup Q$ be a partition of $V(D)$. A $(P,Q)$ vertex-oriented Hamilton cycle in $D$ is a Hamilton cycle $H$ in the graph underlying $D$ such that for each $v \in P$, consecutive arcs of $H$ incident on $v$ do not form a directed path in $D$, and, for each $v \in Q$, consecutive arcs of $H$ incident on $v$ form a directed path in $D$. We give sufficient conditions for the existence of a $(P,Q)$ vertex-oriented Hamilton cycle in $D$ for the cases when $|P| \geq {2\over 3}n$ and when ${1\over 3}n \leq |P| \leq {2\over 3}n$. This sharpens a bound given by Badheka et al.

Détail

DOI : 10.37236/204

Classification : 05C20, 05C45