{
  "id": "1806.00135",
  "version": "v1",
  "published": "2018-05-31T23:30:53.000Z",
  "updated": "2018-05-31T23:30:53.000Z",
  "title": "Packing spanning partition-connected subgraphs with small degrees",
  "authors": [
    "Morteza Hasanvand"
  ],
  "categories": [
    "math.CO"
  ],
  "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,\\ldots, H_m$ such that every graph $H_i$ is $l_i$-partition-connected, where $l_1, l_2,\\ldots, l_m$ are $m$ intersecting supermodular subadditive integer-valued functions on subsets of $V(H)$. These results generalize several known results.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-05-31T23:30:53.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "packing spanning partition-connected subgraphs",
      "small degrees",
      "intersecting supermodular subadditive integer-valued function",
      "spanning subgraph"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}