Bounds for Judicious Balanced Bipartitions of Graphs

Autor: Fayun Cao, Yujiao Luo, Han Ren
Rok vydání: 2018
Předmět:
Zdroj: Graphs and Combinatorics. 34:1175-1184
ISSN: 1435-5914
0911-0119
DOI: 10.1007/s00373-018-1949-x
Popis: A bipartition of the vertex set of a graph is called balanced if the sizes of the sets in the bipartition differ by at most one. Bollob $$\acute{a}$$ s and Scott proved that every regular graph with m edges admits a balanced bipartition $$V_{1}$$ , $$V_{2}$$ of V(G) such that $$\max \{e(V_{1}), e(V_{2}) \}< \frac{m}{4}$$ . Only allowing $$\varDelta (G)-\delta (G)$$ =1 and 2, Yan and Xu, and Hu, He and Hao, respectively showed that a graph G with n vertices and m edges has a balanced bipartition $$V_{1}$$ , $$V_{2}$$ of V(G) such that $$\max \{e(V_{1}), e(V_{2}) \}\le \frac{m}{4}+O(n)$$ . In this paper, we give an upper bound for balanced bipartition of graphs G with $$\varDelta (G)-\delta (G)=t-1$$ , $$t\ge 2$$ is an integer. Our result extends the conclusions above.
Databáze: OpenAIRE
Externí odkaz:
Nepřihlášeným uživatelům se plný text nezobrazuje