.png){kind=icon}
.png){kind=icon}
Return
NON-SEPARATING TREES IN k-CONNECTED GRAPHS
.png){kind=icon}
PRE
AI
DOI：10.7151/dmgt.2637.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
This paper advances the study of connectivity preservation in k-connected graphs by addressing Mader's conjecture on the existence of non-separating trees. We prove that for any k >= 1 and m > 4, every k-connected graph G with minimum degree delta(G) > [(3k) (2)] +m-1 contains a tree T (3) (m-3)-a star-path hybrid structure-such that G-V (T-m-3(3)) remains k-connected. Additionally, we establish the conjecture for the star K-1,K-m-1 and more general trees Ttm-t within a specialized family g of k-connected graphs, where kappa(G(0)(X)) <= k+1 for any subgraph G(0) subset of G and vertex subset X subset of V(G(0)) with |X| = k. Our approach relies on constructing (k + 1)-connected substructures and analyzing their properties to ensure the preservation of k-connectivity after tree removal. These results generalize and strengthen prior work on connectivity keeping trees, providing deeper insights into the structural robustness of highly connected graphs.
Keywords:
connectivity
bipartite graph
fragment
end
Journal
D
IF:
0.8
Papers:
39
Citations:
0