|
Zapiski Nauchnykh Seminarov POMI, 2022, Volume 518, Pages 114–123
(Mi znsl7294)
|
|
|
|
Restriction on minimum degree in the contractible sets problem
N. A. Karol Saint Petersburg State University
Abstract:
Let G be a 3-connected graph. A set W⊂V(G) is contractible if G(W) is connected and G−W is a 2-connected graph. In 1994, McCuaig and Ota formulated the conjecture that, for any k∈N, there exists m∈N such that any 3-connected graph G with v(G)⩾m has a k-vertex contractible set. In this paper we prove that, for any k⩾5, the assertion of the conjecture holds if δ(G)⩾[2k+13]+2.
Key words and phrases:
connectivity, 3-connected graph, contractible subgraph.
Received: 28.11.2022
Citation:
N. A. Karol, “Restriction on minimum degree in the contractible sets problem”, Combinatorics and graph theory. Part XIII, Zap. Nauchn. Sem. POMI, 518, POMI, St. Petersburg, 2022, 114–123
Linking options:
https://www.mathnet.ru/eng/znsl7294 https://www.mathnet.ru/eng/znsl/v518/p114
|
Statistics & downloads: |
Abstract page: | 41 | Full-text PDF : | 10 | References: | 14 |
|