Connectivity keeping edges of trees in 3-connected or 3-edge-connected graphs

DOI10.1016/J.DISC.2024.113913MaRDI QIDQ6204330zbMATH OpenOpenAlexFDO

Authors Qing Yang, Yingzhi Tian

Publication date 27 March 2024

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2303.03896

zbMATH Keywords

3-connected graph3-edge-connected graphconnectivitytrees

Mathematics Subject Classification ID

Combinatorics (05-XX) Graph theory (05Cxx) Algebraic combinatorics (05Exx)

Abstract: Hasunuma [J. Graph Theory 102 (2023) 423-435] conjectured that for any tree $T$ of order $m$, every $k$-connected (or $k$-edge-connected) graph $G$ with minimum degree at least $k+m-1$ contains a tree $T^{\prime }congT$ such that $G-E(T^{\prime })$ is still $k$-connected (or $k$-edge connected). Hasunuma verified this conjecture for $kleq2$. In this paper, we confirm this conjecture for $k=3$.

Recommendations

• Connectivity keeping trees in 3-connected or 3-edge-connected graphs
• Connectivity keeping trees in k-connected graphs
• Connectivity keeping trees in 2-connected graphs
• Connectivity preserving trees in k‐connected or k‐edge‐connected graphs
• Mader's conjecture for graphs with small connectivity

Cites work

• A theorem on n-connected graphs
• Connectivity keeping caterpillars and spiders in 2-connected graphs
• Connectivity keeping caterpillars and spiders in bipartite graphs with connectivity at most three
• Connectivity keeping edges in graphs with large minimum degree
• Connectivity keeping paths in \(k\)-connected bipartite graphs
• Connectivity keeping paths in k-connected graphs
• Connectivity keeping stars or double-stars in 2-connected graphs
• Connectivity keeping trees in 2-connected graphs
• Connectivity keeping trees in 2-connected graphs
• Connectivity keeping trees in 2-connected graphs with girth conditions
• Connectivity keeping trees in k-connected graphs
• Connectivity preserving trees in k‐connected or k‐edge‐connected graphs
• Critically n-Connected Graphs
• Graph theory
• Mader's conjecture for graphs with small connectivity
• Minimally n-line connected graphs.
• Non-separating trees in connected graphs
• Nonseparating trees in 2-connected graphs and oriented trees in strongly connected digraphs

Cited in

(3)

• Connectivity keeping trees in 3-connected or 3-edge-connected graphs
• Connectivity preserving Hamiltonian cycles in \(k\)-connected Dirac graphs
• A survey on the vertex-(edge-)k-maximal graphs and the k-vertex-(edge-)connected graphs with redundant subgraphs

This page was built for publication: Connectivity keeping edges of trees in 3-connected or 3-edge-connected graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6204330)