Vertex-oriented Hamilton cycles in directed graphs (Q2380274): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Latest revision as of 07:56, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Vertex-oriented Hamilton cycles in directed graphs |
scientific article |
Statements
Vertex-oriented Hamilton cycles in directed graphs (English)
0 references
26 March 2010
0 references
Summary: 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 \(\frac23n\) then \(D\) contains an anti-directed Hamilton cycle. This improves a bound of \textit{D. D. Grant} [Ars Comb. 10, 205--209 (1980; Zbl 0448.05034)]. 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 \frac23n\) and when \(\frac13n\leq|P|\leq \frac23n\). This sharpens a bound given by Badheka et al. in [\textit{S. K. Tipnis} and \textit{M. J. Plantholt}, Ars Comb. 83, 257--265 (2007; Zbl 1174.05103)].
0 references