- Title
- An algorithm for the orientation of complete bipartite graphs
- Creator
- Zhao, Lingqi; Wang, Mujiangshan; Zhang, Xuefei; Lin, Yuqing; Wang, Shiying
- Relation
- International Conference on Applied Mathematics, Modelling and Statistics Application (AMMSA 2017). Proceedings of the International Conference on Applied Mathematics, Modelling and Statistics Application (AMMSA 2017) [presented in Advances in Intelligent Research, Vol. 141] (Beijing, China 21-22 May, 2017) p. 361-364
- Publisher Link
- http://dx.doi.org/10.2991/ammsa-17.2017.81
- Publisher
- Atlantis Press
- Resource Type
- conference paper
- Date
- 2017
- Description
- 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.
- Subject
- complete bipartite graph; orientation; algorithm
- Identifier
- http://hdl.handle.net/1959.13/1386965
- Identifier
- uon:32495
- Identifier
- ISBN:9789462523555
- Rights
- © The authors. This article is distributed under the terms of the Creative Commons Attribution License 4.0, which permits non-commercial use, distribution and reproduction in any medium, provided the original work is properly cited. See for details: https://creativecommons.org/licenses/by-nc/4.0/.
- Language
- eng
- Full Text
- Reviewed
- Hits: 6033
- Visitors: 6290
- Downloads: 344
| Thumbnail | File | Description | Size | Format | |||
|---|---|---|---|---|---|---|---|
| View Details Download | ATTACHMENT01 | Publisher version (open access) | 1011 KB | Adobe Acrobat PDF | View Details Download |