Connectivity keeping caterpillars and spiders in bipartite graphs with connectivity at most three

2022/05/01 by Qing Yang, Yang, Qing, Yingzhi Tian +1
Agricultural and Biological Sciences · Biochemistry, Genetics and Molecular Biology · Environmental Science · #Combinatorics (math.CO) #FOS: Mathematics #Forest Insect Ecology and Management #Insect and Arachnid Ecology and Behavior #Plant Parasitism and Resistance

paper · pdf · doi:10.48550/arxiv.2205.00397

openalex publication_date 2022/05/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

A conjecture of Luo, Tian and Wu (2022) says that for every positive integer k and every finite tree T with bipartition X and Y (denote t = max\|X|,|Y |\), every k-connected bipartite graph G with δ(G) ≥ k + t contains a subtree T' ≅ T such that κ(G-V (T')) ≥ k. In this paper, we confirm this conjecture for caterpillars when k=3 and spiders when k≤ 3.

Related

• Connectivity keeping trees in 3-connected bipartite graphs with girth conditions
• Note on the connectivity keeping spiders in k-connected graphs
• Connectivity keeping paths for k-connected bipartite graphs
• On the relation between connectivity, independence and generalized caterpillars
• Connectivity keeping trees in triangle-free graphs