Fujita's connectivity-preserving connected subgraph conjecture

Let kk and mm be positive integers. A graph GG is kk-connected when ba(G)kba(G)\geq k, where ba(G)ba(G) is the minimum size of a vertex set whose deletion disconnects GG or leaves only one vertex; write b4(G)b4(G) for the minimum degree, and let W|W| denote the order of a graph or subgraph WW. Fujita's conjecture. There is a least non-negative integer fk(m)f_k(m) such that every kk-connected graph GG satisfying

b4(G)32k1+fk(m)b4(G)\geq \left\lfloor\frac{3}{2}k\right\rfloor-1+f_k(m)

contains a connected subgraph WW of exact order mm such that GV(W)G-V(W) is still kk-connected. Fujita and Kawarabayashi proposed this as a degree threshold for connectivity-preserving connected subgraphs; it was later confirmed by Mader, who proved fk(m)=mf_k(m)=m and that WW can be chosen to be a path.

Sources & referencesView supporting material

Primary source

Lian Luo, Yingzhi Tian and Liyun Wu, “Connectivity keeping paths in k-connected bipartite graphs”, arXiv:2011.03929 (2021).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.