围长至少是12的平面图的均匀聚集划分

Equitable Cluster Partition of Planar Graphs with Girth at Least 12

中文关键词:  均匀聚集划分  平面图  围长  权转移

英文关键词:equitable cluster partition  planar graph  girth  discharging

中文摘要:

      图$G$的一个均匀$({\mathcal{O}}^{1}_{k}, {\mathcal{O}}^{2}_{k}, \ldots, {\mathcal{O}}^{m}_{k})$-划分是指把图$G$的点集$V(G)$划分成$m$个非空子集$V_{1}$, $V_{2}$, \ldots, $V_{m}$使得对于任意的$\{1, 2, \ldots, m\}$, $G[V_{i}]$都是连通分支的阶数至多是$k$的图, 并且对于任意一对不同的$i, j\in\{1,\ldots, m\}$都有$-1\leq|V_{i}|-|V_{j}|\leq1$, 该划分又叫做均匀$k$聚集$m$-划分. 在本文中, 我们证明了每一个最小度$\delta(G)\geq2$, 围长$g(G)\geq12$的平面图对于任意的整数$m\geq2$都存在一个均匀$({\mathcal{O}}^{1}_{7}, {\mathcal{O}}^{2}_{7}, \ldots, {\mathcal{O}}^{m}_{7})$-划分.

英文摘要:

      An equitable $({\mathcal{O}}^{1}_{k}, {\mathcal{O}}^{2}_{k}, \ldots, {\mathcal{O}}^{m}_{k})$-partition of a graph $G$, which is also called a $k$ cluster $m$-partition, is the partition of $V(G)$ into $m$ non-empty subsets $V_{1}$, $V_{2}$, \ldots, $V_{m}$ such that for every integer $i$ in $\{1, 2, \ldots, m\}$, $G[V_{i}]$ is a graph with components of order at most $k$, and for each distinct pair $i, j$ in $\{1,\ldots, m\}$, there is $-1\leq|V_{i}|-|V_{j}|\leq1$. In this paper, we proved that every planar graph $G$ with minimum degree $\delta(G)\geq2$ and girth $g(G)\geq12$ admits an equitable $({\mathcal{O}}^{1}_{7}, {\mathcal{O}}^{2}_{7}, \ldots, {\mathcal{O}}^{m}_{7})$-partition, for any integer $m\geq2$.