2018/06/19 by Morteza Hasanvand, Hasanvand, Morteza
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO
paper · pdf · doi:10.48550/arxiv.1806.07877
arXiv admin note: text overlap with arXiv:1806.00135
arxiv created 2018/06/19 · arxiv updated 2018/06/22
Let G be a graph and let l be an 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. We say that G is l-rigid, if it contains a spanning l-partition-connected subgraph H with |E(H)|=∑v∈ V(H) l(v)-l(V(H)). In this paper, we investigate decomposition of graphs into spanning partition-connected and spanning rigid subgraphs. As a consequence, we improve a recent result due to Gu (2017) by proving that every (4kp-2p+2m)-connected graph G with k≥ 2 has a spanning subgraph H containing a packing of m spanning trees and p spanning (2k-1)-edge-connected subgraphs H1,…, Hp such that for each vertex v, every Hi-v remains (k-1)-edge-connected and also dH(v)≤ \lceil (dG(v))/(2)\rceil +2kp-p+m. From this result, we refine a result on arc-connected orientations of graphs.