Partitions of multigraphs under degree constraints

Abstract

In 1996, Michael Stiebitz proved that if $G$ is a simple graph with $\delta (G)\ge s+t+1$ and $s,t\in {\mathbb{Z}}_{\ge 0}$, then $V(G)$ can be partitioned into two sets $A$ and $B$ such that $\delta (G[A])\ge s$ and $\delta (G[B])\ge 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)\to r_{>0}$ be a weight function, let $s,t\in {\mathbb{R}}_{\ge 0}$, and let $W={\max }_{e\in E(G)}w(e)$. If $\delta (G)\ge s+t+2W$, then $V(G)$ can be partitioned into two sets $A$ and $B$ such that $\delta (G[A])\ge s$ and $\delta (G[B])\ge t$. This motivated us to consider this partition problem for multigraphs, or equivalently for weighted graphs $(G,w)$ with $w:E(G)\to {\mathbb{Z}}_{\ge 1}$. We prove that if $s,t\in z_{\ge 0}$ and $\delta (G)\ge s+t+2W-1\ge 1$, then $V(G)$ can be partitioned into two sets $A$ and $B$ such that $\delta (G[A])\ge s$ and $\delta (G[B])\ge 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.

References in corpus (1)

• Decomposing Weighted Graphs

Cited by in corpus (1)

• Decomposing $C_4$-free graphs under degree constraints