Partitions of multigraphs under minimum degree constraints
Partitions of multigraphs under minimum degree constraints
复制标题
DOI：
10.1016/j.dam.2018.10.016
复制
发表时间：
2019-03
期刊：
影响因子：
--
通讯作者：
Thomas Schweser;M. Stiebitz
中科院分区：
文献类型：
--
作者：
Thomas Schweser;M. Stiebitz
1996年MichaelStiebitz证明了：如果G是一个简单图，δ（G）≥ s+ t+ 1，且s，t∈ Z 0，则V（G）可划分为两个集合A和B，使得δ（G [A]）≥ s，δ（G [B]）≥ t. 2016年，Amir Ban证明了加权图的类似结果。设G是至少有两个顶点的简单图，w：E（G）→ R> 0是权函数，s，t∈ R≥ 0，W= max e∈ E（G）w（e）.若δ（G）≥ s+ t+ 2 W，则V（G）可划分为两个集合A和B，使得δ（G [A]）≥ s和δ（G [B]）≥ t.这促使我们考虑多重图的划分问题，或者等价地考虑加权图（G，w）的划分问题，其中w：E（G）→ Z≥ 1。证明了：若s，t∈ Z≥ 0且δ（G）≥ s+ t+ 2 W− 1≥ 1，则V（G）可划分为两个集合A和B，使得δ（G [A]）≥ s，δ（G [B]）≥ t.我们还证明了这个结果的一个可变版本，并表明对于K4 −-free图，最小度的界可以减小。
Abstract In 1996, Michael Stiebitz proved that if G is a simple graph with δ (G)≥ s+ t+ 1 and s, t∈ Z 0, then V (G) can be partitioned into two sets A and B such that δ (G [A])≥ s and δ (G [B])≥ t. In 2016, Amir Ban proved a similar result for weighted graphs. Let G be a simple graph with at least two vertices, let w: E (G)→ R> 0 be a weight function, let s, t∈ R≥ 0, and let W= max e∈ E (G) w (e). If δ (G)≥ s+ t+ 2 W, then V (G) can be partitioned into two sets A and B such that δ (G [A])≥ s and δ (G [B])≥ t. This motivated us to consider this partition problem for multigraphs, or equivalently for weighted graphs (G, w) with w: E (G)→ Z≥ 1. We prove that if s, t∈ Z≥ 0 and δ (G)≥ s+ t+ 2 W− 1≥ 1, then V (G) can be partitioned into two sets A and B such that δ (G [A])≥ s and δ (G [B])≥ t. We also prove a variable version of this result and show that for K 4−-free graphs, the bound on the minimum degree can be decreased.