Bounds for the number of meeting edges in graph partitioning |
| |
Authors: | Qinghou Zeng Jianfeng Hou |
| |
Institution: | 1.Center for Discrete Mathematics,Fuzhou University,Fuzhou, Fujian,P.R. China |
| |
Abstract: | Let G be a weighted hypergraph with edges of size at most 2. Bollobás and Scott conjectured that G admits a bipartition such that each vertex class meets edges of total weight at least (w 1?Δ1)/2+2w 2/3, where wi is the total weight of edges of size i and Δ1 is the maximum weight of an edge of size 1. In this paper, for positive integer weighted hypergraph G (i.e., multi-hypergraph), we show that there exists a bipartition of G such that each vertex class meets edges of total weight at least (w 0?1)/6+(w 1?Δ1)/3+2w 2/3, where w 0 is the number of edges of size 1. This generalizes a result of Haslegrave. Based on this result, we show that every graph with m edges, except for K 2 and K 1,3, admits a tripartition such that each vertex class meets at least 2m/5] edges, which establishes a special case of a more general conjecture of Bollobás and Scott. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|