LARGE CONTRACTIBLE SUBGRAPHS OF A 3-CONNECTED GRAPH

被引：1

作者：

Karpov, Dmitri, V ^{[1
,2
]}

机构：

[1] Russian Acad Sci, St Petersburg Dept, VA Steklov Inst Math, St Petersburg, Russia

[2] St Petersburg Univ, St Petersburg, Russia

来源：

DISCUSSIONES MATHEMATICAE GRAPH THEORY | 2021年 / 41卷 / 01期

关键词：

connectivity; 3-connected graph; contractible subgraph;

D O I：

10.7151/dmgt.2172

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

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 <= vertical bar W vertical bar <= 2m - 4. (Recall that a set W subset of 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.

引用

页码：83 / 101

页数：19

共 13 条

[1]

Harary F., 1969, Graph Theory

[2]

HOHBERG W, 1992, DISCRETE MATH, V109, P133

[3]

Karpov D. V., 2005, J MATH SCI, V126, P1167

[4]

Karpov D.V., 2015, J MATH SCI, V204, P232

[5]

Karpov DV, 2013, J MATH SCI, V417, P106, DOI [10.1007/s10958-014-2199-y, DOI 10.1007/S10958-014-2199-Y]

[6]

Karpov DV, 2011, J MATH SCI, V391, P90, DOI [10.1007/s10958-012-0885-1, DOI 10.1007/S10958-012-0885-1]

[7]

KARPOV DV, 2003, J MATH SCI, V113, P584

[8]

Karpov DV, 2006, J MATH SCI, V340, P33, DOI DOI 10.1007/S10958-007-0330-Z

[9] Contractible subgraphs in 3-connected graphs [J].

Kriesell, M .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 2000, 80 (01) :32-48

[10] On small contractible subgraphs in 3-connected graphs of small average degree [J].

Kriesell, Matthias .

GRAPHS AND COMBINATORICS, 2007, 23 (05) :545-557

← 1 2 →