|
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 \subset 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 \in \mathbb{N}$, there exists $m \in \mathbb{N}$ such that any $3$-connected graph $G$ with $v(G) \geqslant m$ has a $k$-vertex contractible set. In this paper we prove that, for any $k \geqslant 5$, the assertion of the conjecture holds if $\delta(G) \geqslant \left[ \frac{2k + 1}{3} \right] + 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: | 39 | Full-text PDF : | 9 | References: | 13 |
|