Fujita's connectivity-preserving connected subgraph conjecture
Let and be positive integers. A graph is -connected when , where is the minimum size of a vertex set whose deletion disconnects or leaves only one vertex; write for the minimum degree, and let denote the order of a graph or subgraph . Fujita's conjecture. There is a least non-negative integer such that every -connected graph satisfying
contains a connected subgraph of exact order such that is still -connected. Fujita and Kawarabayashi proposed this as a degree threshold for connectivity-preserving connected subgraphs; it was later confirmed by Mader, who proved and that can be chosen to be a path.
References
Status
- Solved: W. Mader. Connectivity keeping paths in k-connected graphs (Journal of Graph Theory, 2010) https://onlinelibrary.wiley.com/doi/10.1002/jgt.20465
Source: Lian Luo, Yingzhi Tian and Liyun Wu, “Connectivity keeping paths in k-connected bipartite graphs”, arXiv:2011.03929 (2021).
Progress summary
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.