Abstract <p>For integers <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(m\)</EquationSource>  </InlineEquation> and <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(n,\)</EquationSource>  </InlineEquation> where <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(2 \leqslant m \leqslant n\)</EquationSource>  </InlineEquation> and <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(n \geqslant 3\)</EquationSource>  </InlineEquation>, <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\(D\left( {n,m} \right)\)</EquationSource>  </InlineEquation> denotes the digraph obtained by reversing the direction of <InlineEquation ID="IEq6"> <EquationSource Format="TEX">\(m - 1\)</EquationSource>  </InlineEquation> consecutive arcs of a directed cycle of length <InlineEquation ID="IEq7"> <EquationSource Format="TEX">\(n\)</EquationSource>  </InlineEquation>. Let <InlineEquation ID="IEq8"> <EquationSource Format="TEX">\(D\)</EquationSource>  </InlineEquation> be an oriented graph of order <InlineEquation ID="IEq9"> <EquationSource Format="TEX">\(p \geqslant 3\)</EquationSource>  </InlineEquation> with the minimum out-degree and in-degree at least <InlineEquation ID="IEq10"> <EquationSource Format="TEX">\(\left\lfloor {p{\text{/2}}} \right\rfloor - 1\)</EquationSource>  </InlineEquation>. We introduce and study the following conjecture: for every <InlineEquation ID="IEq11"> <EquationSource Format="TEX">\(3 \leqslant n \leqslant p\)</EquationSource>  </InlineEquation> and <InlineEquation ID="IEq12"> <EquationSource Format="TEX">\(2 \leqslant m \leqslant n\)</EquationSource>  </InlineEquation>, <InlineEquation ID="IEq13"> <EquationSource Format="TEX">\(D\)</EquationSource>  </InlineEquation> contains a <InlineEquation ID="IEq14"> <EquationSource Format="TEX">\(D\left( {n,m} \right)\)</EquationSource>  </InlineEquation>. In this paper, we show that if <InlineEquation ID="IEq15"> <EquationSource Format="TEX">\(p \geqslant 10\)</EquationSource>  </InlineEquation> and <InlineEquation ID="IEq16"> <EquationSource Format="TEX">\(m = 3\)</EquationSource>  </InlineEquation>, then this conjecture is true, i.e., <InlineEquation ID="IEq17"> <EquationSource Format="TEX">\(D\)</EquationSource>  </InlineEquation> contains a subdigraph obtained from a Hamiltonian cycle of <InlineEquation ID="IEq18"> <EquationSource Format="TEX">\(D\)</EquationSource>  </InlineEquation> by reversing the direction of two consecutive arcs. We present examples of oriented graphs showing that this result is sharp in the following sense: both lower bounds <InlineEquation ID="IEq19"> <EquationSource Format="TEX">\(\left\lfloor {p{\text{/2}}} \right\rfloor - 1\)</EquationSource>  </InlineEquation> and 10 are tight. We also suggest some conjectures and problems.</p>

On Special Suborgraphs in Orgraphs with Large Semidegrees

期刊论文
发表日期：

2025年12月1日

查看全文

Samvel Darbinyan

摘要

Abstract

For integers \(m\) and \(n,\) where \(2 \leqslant m \leqslant n\) and \(n \geqslant 3\) , \(D\left( {n,m} \right)\) denotes the digraph obtained by reversing the direction of \(m - 1\) consecutive arcs of a directed cycle of length \(n\) . Let \(D\) be an oriented graph of order \(p \geqslant 3\) with the minimum out-degree and in-degree at least \(\left\lfloor {p{\text{/2}}} \right\rfloor - 1\) . We introduce and study the following conjecture: for every \(3 \leqslant n \leqslant p\) and \(2 \leqslant m \leqslant n\) , \(D\) contains a \(D\left( {n,m} \right)\) . In this paper, we show that if \(p \geqslant 10\) and \(m = 3\) , then this conjecture is true, i.e., \(D\) contains a subdigraph obtained from a Hamiltonian cycle of \(D\) by reversing the direction of two consecutive arcs. We present examples of oriented graphs showing that this result is sharp in the following sense: both lower bounds \(\left\lfloor {p{\text{/2}}} \right\rfloor - 1\) and 10 are tight. We also suggest some conjectures and problems.