Covering of graphs by complete bipartite subgraphs; Complexity of 0–1 matrices |
| |
| Authors: | Zsolt Tuza |
| |
| Affiliation: | (1) Computer and Automation Institute of the Hungarian Academy of Sciences, Kende u. 13–17, H-1111 Budapest, Hungary |
| |
| Abstract: | We prove that the edge set of an arbitrary simple graphG onn vertices can be covered by at mostn−[log2 n]+1 complete bipartite subgraphs ofG. If the weight of a subgraph is the number of its vertices, then there always exists a cover with total weightc(n 2/logn) and this bound is sharp apart from a constant factor. Our result answers a problem of T. G. Tarján. Dedicated to Paul Erdős on his seventieth birthday |
| |
| Keywords: | 05 C 35 15 A 99 |
| 本文献已被 SpringerLink 等数据库收录！ |
|
