2022/05/10 by Hasanvand, Morteza
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2205.05044
Let G be a graph with a spanning subgraph F, let m be a positive integer, and let f be a positive integer-valued function on V(G). In this paper, we show that if for all S⊆ V(G), Ωm(G∖ S)≤ ∑v∈ S(f(v)-2m)+m+Ωm(G[S]), then G has a spanning m-tree-connected subgraph H containing F such that for each vertex v, dH(v)≤ f(v)+max\0,dF(v)-m\, where G[S] denotes the induced subgraph of G with the vertex set S and Ωm(G0) is a parameter to measure m-tree-connectivity of a given graph G0. By applying this result, we show that every k-edge-connected graph G with k≥ 2m has a spanning m-tree-connected subgraph H such that dH(v)≤ \lceil (m)/(k)(dG(v)-2m)\rceil+2m for each v∈ V(H); moreover, if G is k-tree-connected and k≥ m, then G has a spanning m-tree-connected subgraph H such that dH(v)≤ \lceil (m)/(k)(dG(v)-m)\rceil+m for each v∈ V(H). As a consequence, we conclude that every (r-2m)-edge-connected graph with r≥ 4m admits a spanning m-tree-connected subgraph with maximum degree at most 3m. Next, we prove that a graph G admits a spanning m-tree-connected subgraph H satisfying Δ(H) ≤ 2m+1, if for all S⊆ V(G), ω(G∖ S)+\small (m+1)/(2) iso(G∖ S) ≤ (1)/(m)|S|+1, where ω(G∖ S) and iso(G∖ S) denote the number of components and the number of isolated vertices of G∖ S, respectively. As a consequence, we conclude that every m(n-1)-connected K1, n-free simple graph with a sufficiently large minimum degree and n≥ 3 admits a spanning m-tree-connected subgraph with maximum degree at most 2m+1.