Fujita's connectivity-preserving connected subgraph conjecture
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.
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.