Packing spanning partition-connected subgraphs with small degrees

Abstract

Let $G$ be a graph with $X\subseteq V(G)$ and let $l$ be an intersecting supermodular subadditive integer-valued function on subsets of $V(G)$. The graph $G$ is said to be $l$-partition-connected, if for every partition $P$ of $V(G)$, $e_G(P)\ge {\sum }_{A\in P}l(A)-l(V(G))$, where $e_G(P)$ denotes the number of edges of $G$ joining different parts of $P$. Let $\lambda \in [0,1]$ be a real number and let $\eta$ be a real function on $X$. In this paper, we show that if $G$ is $l$-partition-connected and for all $S\subseteq X$, $${\Theta }_l(G\setminus S)\le \sum _{v\in S}(\eta (v)-2l(v))+l(V(G))+l(S)-\lambda (e_G(S))+l(S)),$$ then $G$ has an $l$-partition-connected spanning subgraph $H$ such that for each vertex $v\in X$, $d_H(v)\le \lceil \eta (v)-\lambda l(v)\rceil$, where $e_G(S)$ denotes the number of edges of $G$ with both ends in $S$ and ${\Theta }_l(G\setminus S)$ denotes the maximum number of all ${\sum }_{A\in P}l(A)-e_{G\setminus S}(P)$ taken over all partitions $P$ of $V(G)\setminus S$. Finally, we show that if $H$ is an $(l_1+\cdots +l_m)$-partition-connected graph, then it can be decomposed into $m$ edge-disjoint spanning subgraphs $H_1,\dots ,H_m$ such that every graph $H_i$ is $l_i$-partition-connected, where $l_1,l_2,\dots ,l_m$ are $m$ intersecting supermodular subadditive integer-valued functions on subsets of $V(H)$. These results generalize several known results.

Cited by in corpus (1)

• Bipartite partition-connected factors with small degrees