Vertex-oriented Hamilton cycles in directed graphs

MaRDI QIDQ2380274zbMATH OpenFDO

Authors Michael J. Plantholt, Shailesh K. Tipnis

Publication date 26 March 2010

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/228919, http://www.emis.de/journals/EJC/Volume_16/Abstracts/v16i1r115.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Eulerian and Hamiltonian graphs (05C45)

Review text

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)].

Recommendations

• Semi-degree threshold for anti-directed Hamiltonian cycles
• Improved sufficient conditions for the existence of anti-directed Hamiltonian cycles in digraphs
• On the Dirac-type conjecture for anti-directed Hamiltonian digraphs
• Arbitrary orientations of Hamilton cycles in digraphs
• scientific article; zbMATH DE number 1047732

Cited in

(8)

• Anti-Eulerian digraphs
• Improved sufficient conditions for the existence of anti-directed Hamiltonian cycles in digraphs
• On the Dirac-type conjecture for anti-directed Hamiltonian digraphs
• A sufficient condition for the existence of an anti-directed 2-factor in a directed graph
• Oriented hamilton cycles in digraphs
• Antidirected Hamiltonian paths and cycles of digraphs with \(\alpha_2\)-stable number 2
• Antidirected spanning trail of digraphs with _2-stable number 3
• Semi-degree threshold for anti-directed Hamiltonian cycles

This page was built for publication: Vertex-oriented Hamilton cycles in directed graphs

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