<p>In 1978, Chvátal and Thomassen proved that each bridgeless undirected graph <i>G</i> has an orientation with radius at most <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2959_Article_IEq1.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="130" /> </InlineMediaObject> <EquationSource Format="TEX">\(rad(G)^2+rad(G)\)</EquationSource> </InlineEquation>. In 1985, Chung, Garey, and Tarjan extended the work of Chvátal and Thomassen to mixed graphs, and proved that each bridgeless mixed graph <i>G</i> has an orientation with radius at most <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2959_Article_IEq2.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="146" /> </InlineMediaObject> <EquationSource Format="TEX">\(4rad(G)^2+4rad(G)\)</EquationSource> </InlineEquation>. Recently, Czabarka, Dankelmann, and Székely determined the minimum degree threshold for an undirected graph of order <i>n</i> to have oriented diameter two. Chen and Chang gave a sufficient condition regarding the minimum degree for an undirected bipartite graph to have oriented diameter three, and determined the minimum degree threshold for such a graph to have oriented diameter three. In this paper, we extend the work of Chen and Chang to mixed graphs, and give a sufficient condition regarding the minimum degree for a mixed bipartite graph to have oriented diameter three. In particular, we established a sufficient bound and provided constructions showing that the bound is close to best possible.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Diameter Three Orientability of Mixed Bipartite Graphs

  • Hengzhe Li,
  • Zhiwei Ding,
  • Jianbing Liu,
  • An Chang

摘要

In 1978, Chvátal and Thomassen proved that each bridgeless undirected graph G has an orientation with radius at most \(rad(G)^2+rad(G)\) . In 1985, Chung, Garey, and Tarjan extended the work of Chvátal and Thomassen to mixed graphs, and proved that each bridgeless mixed graph G has an orientation with radius at most \(4rad(G)^2+4rad(G)\) . Recently, Czabarka, Dankelmann, and Székely determined the minimum degree threshold for an undirected graph of order n to have oriented diameter two. Chen and Chang gave a sufficient condition regarding the minimum degree for an undirected bipartite graph to have oriented diameter three, and determined the minimum degree threshold for such a graph to have oriented diameter three. In this paper, we extend the work of Chen and Chang to mixed graphs, and give a sufficient condition regarding the minimum degree for a mixed bipartite graph to have oriented diameter three. In particular, we established a sufficient bound and provided constructions showing that the bound is close to best possible.