- Tytuł:
- Large Contractible Subgraphs of a 3-Connected Graph
- Autorzy:
- Karpov, Dmitri V.
- Powiązania:
- https://bibliotekanauki.pl/articles/32083775.pdf
- Data publikacji:
- 2021-02-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
connectivity
3-connected graph
contractible subgraph - Opis:
- Let m ≥ 5 be a positive integer and let G be a 3-connected graph on at least 2m + 1 vertices. We prove that G has a contractible set W such that m ≤ |W| ≤ 2m − 4. (Recall that a set W ⊂ V (G) of a 3-connected graph G is contractible if the graph G(W) is connected and the graph G − W is 2-connected.) A particular case for m = 4 is that any 3-connected graph on at least 11 vertices has a contractible set of 5 or 6 vertices.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2021, 41, 1; 83-101
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł