Tight upper bound on the number of edges in a bipartite K3,3-free or K5-free graph with an application |
| |
| Authors: | Zhi-Zhong Chen Shiqing Zhang |
| |
| Affiliation: | a Department of Mathematical Sciences, Tokyo Denki University, Hatoyama, Saitama 350-0394, Japan
b Department of Computers, Dandong Institute of Technical Skills, Dandong City, People's Republic of China |
| |
| Abstract: | We show that an n-vertex bipartite K3,3-free graph with n?3 has at most 2n−4 edges and that an n-vertex bipartite K5-free graph with n?5 has at most 3n−9 edges. These bounds are also tight. We then use the bound on the number of edges in a K3,3-free graph to extend two known NC algorithms for planar graphs to K3,3-free graphs. |
| |
| Keywords: | Algorithms Bipartite graphs Edge bound |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
