2018/05/31 by Morteza Hasanvand, Hasanvand, Morteza · 1 citation
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO
paper · pdf · doi:10.48550/arxiv.1806.00135
arxiv created 2018/05/31 · arxiv updated 2018/06/04
Let G be a graph with X⊆ 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), eG(P)≥ ∑A∈ P l(A)-l(V(G)), where eG(P) denotes the number of edges of G joining different parts of P. Let λ∈ [0,1] be a real number and let η be a real function on X. In this paper, we show that if G is l-partition-connected and for all S⊆ X, Θl(G ∖ S) ≤ ∑v∈ S (η(v) -2l(v))+l(V(G))+l(S)-λ(eG(S))+l(S)), then G has an l-partition-connected spanning subgraph H such that for each vertex v∈ X, dH(v)≤ \lceil η(v) -λl(v) \rceil , where eG(S) denotes the number of edges of G with both ends in S and Θl(G ∖ S) denotes the maximum number of all ∑A∈ P l(A)-eG∖ S(P) taken over all partitions P of V(G)∖ S. Finally, we show that if H is an (l1+⋯ +lm)-partition-connected graph, then it can be decomposed into m edge-disjoint spanning subgraphs H1,…, Hm such that every graph Hi is li-partition-connected, where l1, l2,…, lm are m intersecting supermodular subadditive integer-valued functions on subsets of V(H). These results generalize several known results.