Connectivity keeping trees in 3-connected bipartite graphs with girth conditions

2023/04/23 by Yang, Qing, Tian, Yingzhi
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2304.11596

Abstract

Luo, Tian and Wu conjectured in 2022 that for any tree T with bipartition X and Y, every k-connected bipartite graph G with δ(G) ≥ k + t, where t = max\|X|,|Y |\, contains a subtree T' ≅ T such that G-V(T') remains k-connected. This conjecture has been proved for caterpillars and spiders when k≤ 3; and for paths with odd order. In this paper, we prove that this conjecture holds if G is a bipartite graph with g(G)≥ diam(T)-1 and k≤ 3, where g(G) and diam(T) denote the girth of G and the diameter of T, respectively.

Related

• Connectivity keeping caterpillars and spiders in bipartite graphs with connectivity at most three
• Connectivity keeping paths for k-connected bipartite graphs
• Connectivity keeping trees in triangle-free graphs
• Proof a conjecture on connectivity keeping odd paths in k-connected bipartite graphs
• Connectivity keeping edges of trees in 3-connected or 3-edge-connected graphs