Strong $k$-transitive oriented graphs with large minimum degree
Author(s):
Article Type:
Research/Original Article (دارای رتبه معتبر)
Abstract:
A digraph $D=(V,E)$ is $k$-transitive if for any directed $uv$-path of length $k$, we have $(u,v) \in E$. In this paper, we study the structure of strong $k$-transitive oriented graphs having large minimum in- or out-degree. We show that such oriented graphs are \emph{extended cycles}. As a consequence, we prove that Seymour's Second Neighborhood Conjecture (SSNC) holds for $k$-transitive oriented graphs for $k \leq 11$. Also we confirm Bermond--Thomassen Conjecture for $k$-transitive oriented graphs for $k \leq 11$. A characterization of $k$-transitive oriented graphs having a hamiltonian cycle for $k \leq 6$ is obtained immediately.
Keywords:
Language:
English
Published:
Communications in Combinatorics and Optimization, Volume:10 Issue: 3, Summer 2025
Pages:
681 to 693
https://www.magiran.com/p2814627