|
|
Pure Mathematics 2024
一些图的弱外部平衡划分
|
Abstract:
设G是一个图。G的一个2-划分是V(G)的一个2-划分，即V(G)=V1∪V2且V1∩V2= ？。如果一个2-划分满足||V1|-|V2||≤1，我们就称其为平衡划分。本文的研究主要基于Bollobás和Scott提出的一个猜想：每个图G都有一个平衡划分(V1,V2)，对于V1中的每一个顶点v，v的邻点中至少有一半减去一个在V2中；对于V2中的每一个顶点v，v的邻点中至少有一半减去一个在V1中。在本文中，将对二部图、皇冠图以及风车图证实这一猜想。
Let G be a graph. A bipartition of G is a bipartition of V(G) with V(G)=V1∪V2 and V1∩V2= ？. If a bipartition satisfies ||V1|-|V2||≤1, we call it a bisection. The research in this paper is mainly based on a conjecture proposed by Bollobás and Scott: every graph G has a bisection (V1,V2) such that ？v∈V1, at least half minus one of the neighbors of v are in the V2;？v∈V2, at least half minus one of the neighbors of v are in the V1. In this paper, we confirm this conjecture for some bipartite graphs, crown graphs and windmill graphs.
| [1] | Shelah, S. and Milner, E.C. (1990) Graphs with No Unfriendly Partitions. In: Baker, A., Bollobás, B. and Hajnal, A., Eds., A Tribute to Paul Erd？s, Cambridge University Press, Cambridge, 373-384.
https://doi.org/10.1017/CBO9780511983917.031 |
| [2] | Aharoni, R., Milner, E.C. and Prikry, K. (1990) Unfriendly Partitions of a Graph. Journal of Combinatorial Theory, Series B, 50, 1-10. https://doi.org/10.1016/0095-8956(90)90092-E |
| [3] | Aurichi, L.F. and Real, L.S.S. (2023) Unfriendly Partitions When Avoiding Vertices of Finite Degree. Journal of Logic and Computation, 2023, exad070. https://doi.org/10.1093/logcom/exad070 |
| [4] | Ban, A. and Linial, N. (2016) Internal Partitions of Regular Graphs. Journal of Graph Theory, 83, 5-18.
https://doi.org/10.1002/jgt.21909 |
| [5] | Bollobás, B. and Scott, A.D. (2002) Problems and Results on Judicious Partitions. Random Structures & Algorithms, 21, 414-430. https://doi.org/10.1002/rsa.10062 |
| [6] | Esperet, L., Mazzuoccolo, G. and Tarsi, M. (2017) Flows and Bisections in Cubic Graphs. Journal of Graph Theory, 86, 149-158. https://doi.org/10.1002/jgt.22118 |
| [7] | 周新航. 皇冠图 的邻点可区别关联色数[J]. 山东理工大学学报(自然科学版), 2009(23): 40-43. |
| [8] | Ji, Y., Ma, J., Yan, J. and Yu, X. (2019) On Problems about Judicious Bipartitions of Graphs. Journal of Combinatorial Theory, Series B, 139, 230-250 https://doi.org/10.1016/j.jctb.2019.03.001 |
