An Algorithm for the Orientation of Complete Bipartite Graphs
Authors
Lingqi Zhao, Mujiangshan Wang, Xuefei Zhang, Yuqing Lin, Shiying Wang
Corresponding Author
Lingqi Zhao
Available Online May 2017.
- DOI
- 10.2991/ammsa-17.2017.81How to use a DOI?
- Keywords
- complete bipartite graph; orientation; algorithm
- Abstract
Let G be a graph with vertex set V(G) and edge set E(G). We consider the problem of orienting the edges of a complete bipartite graph Kn,n so only two different in-degrees a and b occur. An obvious necessary condition for orienting the edges of G so that only two in-degrees a and b occur, is that there exist positive integers s and t satisfying s+t=|V(G)| and as+bt=|V(G)|. In this paper, we show that the necessary condition is also sufficient for a complete bipartite graph Kn,n. Furthermore, we give the algorithms of orientations with only two in-degrees of Kn,n.
- Copyright
- © 2017, the Authors. Published by Atlantis Press.
- Open Access
- This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).
Cite this article
TY - CONF AU - Lingqi Zhao AU - Mujiangshan Wang AU - Xuefei Zhang AU - Yuqing Lin AU - Shiying Wang PY - 2017/05 DA - 2017/05 TI - An Algorithm for the Orientation of Complete Bipartite Graphs BT - Proceedings of the 2017 International Conference on Applied Mathematics, Modelling and Statistics Application (AMMSA 2017) PB - Atlantis Press SP - 361 EP - 364 SN - 1951-6851 UR - https://doi.org/10.2991/ammsa-17.2017.81 DO - 10.2991/ammsa-17.2017.81 ID - Zhao2017/05 ER -