| 刘晓玲,孙磊,郑伟.围长至少是12的平面图的均匀聚集划分[J].数学研究及应用,2024,44(2):152~160 |
| 围长至少是12的平面图的均匀聚集划分 |
| Equitable Cluster Partition of Planar Graphs with Girth at Least 12 |
| 投稿时间：2023-03-22 修订日期：2023-12-15 |
| DOI：10.3770/j.issn:2095-2651.2024.02.002 |
| 中文关键词: 均匀聚集划分 平面图 围长 权转移 |
| 英文关键词:equitable cluster partition planar graph girth discharging |
| 基金项目:国家自然科学基金(Grant Nos.12071265; 12271331), 山东省自然科学基金青年基金(Grant No.ZR202102250232). |
|
| 摘要点击次数: 128 |
| 全文下载次数: 199 |
| 中文摘要: |
| 图$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$. |
| 查看全文 查看/发表评论 下载PDF阅读器 |
|
|
|
