Antipaths in oriented graphs

DOI10.1016/J.DISC.2023.113515zbMATH Open1516.05109arXiv2212.09876OpenAlexW4379356442MaRDI QIDQ6098098FDOQ6098098

Authors: Tereza Klimošová, Maya Stein 

Publication date: 12 June 2023

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

Abstract: We show that for any natural number $kge1$, any oriented graph $D$ of minimum semidegree at least $(3k-2)/4$ contains an antidirected path of length $k$. In fact, a slightly weaker condition on the semidegree sequence of $D$ suffices, and as a consequence, we confirm a weakened antidirected path version of a conjecture of Addario-Berry, Havet, Linhares Sales, Thomass'e and Reed.

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

Recommendations

• scientific article; zbMATH DE number 1092941
• Longest paths and cycles in bipartite oriented graphs
• Semi-degree threshold for anti-directed Hamiltonian cycles
• Digraphs without directed path of length two or three
• scientific article; zbMATH DE number 2188371

zbMATH Keywords

oriented graphantidirected pathsemidegree

Mathematics Subject Classification ID

Distance in graphs (05C12) Paths and cycles (05C38)

Cites Work

• Some Theorems on Abstract Graphs
• Oriented trees in digraphs
• Title not available (Why is that?)
• An exact minimum degree condition for Hamilton cycles in oriented graphs
• Title not available (Why is that?)
• Hamilton Cycles in Oriented Graphs
• A Dirac-Type Result on Hamilton Cycles in Oriented Graphs
• Title not available (Why is that?)
• Oriented hamilton cycles in digraphs
• Arbitrary orientations of Hamilton cycles in oriented graphs
• Long paths and cycles in oriented graphs
• Tree containment and degree conditions

Cited In (4)

• Title not available (Why is that?)
• Antidirected subgraphs of oriented graphs
• On finding the longest antisymmetric path in directed acyclic graphs
• Antidirected spanning closed trail in tournaments

This page was built for publication: Antipaths in oriented graphs

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