Oriented bipartite graphs and the Goldbach graph
Oriented bipartite graphs and the Goldbach graph
复制标题
有向二部图和哥德巴赫图
DOI：
10.1016/j.disc.2021.112497
复制
发表时间：
2021
影响因子：
0.8
通讯作者：
Sen, Sagnik
中科院分区：
文献类型：
--
作者：
Das, Sandip;Ghosh, Prantar;Ghosh, Shamik;Sen, Sagnik
本文研究了定向二部图。特别是，我们引入“双传递”图。得到了双传递双凸性的几个刻画。我们证明了双传递重名等价于无环重名。作为应用，我们用Hamilton路刻画了无圈双拓扑，确定了给定阶的非同构无圈双拓扑的个数，并在线性时间内解决了无圈双拓扑的图同构问题.接下来，我们证明了著名的Caccetta-Häggkvist猜想定向二部图在某些情况下，它是未解决的，在一般情况下，定向图。我们还介绍了无向以及定向的“奇-偶”图的概念。利用它们刻画了偶图和无圈定向偶图。事实上，我们证明了任何二部图（无圈定向二部图）都可以用某个奇偶图（定向奇偶图）来表示。得到了奇偶图连通的一些条件。研究奇偶图及其连通性的动机是一类特殊的奇偶图，我们称之为“哥德巴赫图”。我们证明了著名的哥德巴赫猜想等价于哥德巴赫图的连通性。一些其他的数论原理（例如，孪生素数猜想）与哥德巴赫图的各种参数有关，激发了我们研究哥德巴赫图的顶点度和独立集的性质.最后，我们观察了一些与哥德巴赫图有关的奇偶图在少量顶点时的哈密顿性质。
In this paper, we study oriented bipartite graphs. In particular, we introduce “bitransitive” graphs. Several characterizations of bitransitive bitournaments are obtained. We show that bitransitive bitounaments are equivalent to acyclic bitournaments. As applications, we characterize acyclic bitournaments with Hamiltonian paths, determine the number of non-isomorphic acyclic bitournaments of a given order, and solve the graph-isomorphism problem in linear time for acyclic bitournaments. Next, we prove the well-known Caccetta-Häggkvist Conjecture for oriented bipartite graphs in some cases for which it is unsolved, in general, for oriented graphs. We also introduce the concept of undirected as well as oriented “odd-even” graphs. We characterize bipartite graphs and acyclic oriented bipartite graphs in terms of them. In fact, we show that any bipartite graph (acyclic oriented bipartite graph) can be represented by some odd-even graph (oriented odd-even graph). We obtain some conditions for connectedness of odd-even graphs. This study of odd-even graphs and their connectedness is motivated by a special family of odd-even graphs which we call “Goldbach graphs”. We show that the famous Goldbach's conjecture is equivalent to the connectedness of Goldbach graphs. Several other number theoretic conjectures (e.g., the twin prime conjecture) are related to various parameters of Goldbach graphs, motivating us to study the nature of vertex-degrees and independent sets of these graphs. Finally, we observe Hamiltonian properties of some odd-even graphs related to Goldbach graphs for a small number of vertices.