|
Zapiski Nauchnykh Seminarov POMI, 2022, Volume 518, Pages 5–93
(Mi znsl7292)
|
|
|
|
This article is cited in 1 scientific paper (total in 1 paper)
Every $3$-connected graph on at least $13$ vertices has a contractible set on $5$ vertices
N. Yu. Vlasova St. Petersburg Department of Steklov Mathematical Institute of Russian Academy of Sciences
Abstract:
A subset $H$ of the set of vertices of a $3$-connected finite graph $G$ is called contractible if $G(H)$ is connected and $G - H$ is $2$-connected. We prove that every $3$-connected graph on at least $13$ vertices has a contractible set on $5$ vertices. And there is a $3$-connected graph on $12$ vertices that does not contain a contractible set on $5$ vertices.
Key words and phrases:
connectivity, $3$-connected graph, contractible subgraph.
Received: 26.09.2022
Citation:
N. Yu. Vlasova, “Every $3$-connected graph on at least $13$ vertices has a contractible set on $5$ vertices”, Combinatorics and graph theory. Part XIII, Zap. Nauchn. Sem. POMI, 518, POMI, St. Petersburg, 2022, 5–93
Linking options:
https://www.mathnet.ru/eng/znsl7292 https://www.mathnet.ru/eng/znsl/v518/p5
|
Statistics & downloads: |
Abstract page: | 47 | Full-text PDF : | 21 | References: | 13 |
|