Let G be a 3-connected graph. A set <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$W \subset V(G)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>W</mi> <mo>⊂</mo> <mi>V</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> is called contractible if G(W) is a connected graph and <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$G - W$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>G</mi> <mo>-</mo> <mi>W</mi> </mrow> </math></EquationSource> </InlineEquation> is a 2-connected graph. In 1994, McCuaig and Ota conjectured that for any <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$k \in \mathbb {N}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>k</mi> <mo>∈</mo> <mi mathvariant="double-struck">N</mi> </mrow> </math></EquationSource> </InlineEquation> there exists <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$n \in \mathbb {N}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>∈</mo> <mi mathvariant="double-struck">N</mi> </mrow> </math></EquationSource> </InlineEquation> such that any 3-connected graph G with <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$v(G) \ge n$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>v</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> <mo>≥</mo> <mi>n</mi> </mrow> </math></EquationSource> </InlineEquation> has a k-vertex contractible set. It is proved that this holds if <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$k \ge 5$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>k</mi> <mo>≥</mo> <mn>5</mn> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$\delta (G) \ge \left[ \frac{2k + 1}{3} \right] + 2$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>δ</mi> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <mo>≥</mo> <mfenced close="]" open="["> <mfrac> <mrow> <mn>2</mn> <mi>k</mi> <mo>+</mo> <mn>1</mn> </mrow> <mn>3</mn> </mfrac> </mfenced> <mo>+</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation>. Bibliography: 9 titles.

RESTRICTION ON MINIMUM DEGREE IN THE CONTRACTIBLE SETS PROBLEM

期刊论文
发表日期：

2026年3月11日

查看全文

N. A. Karol

摘要

Let G be a 3-connected graph. A set $W \subset V(G)$ $W \subset V (G)$ is called contractible if G(W) is a connected graph and $G - W$ $G - W$ is a 2-connected graph. In 1994, McCuaig and Ota conjectured that for any $k \in \mathbb {N}$ $k \in N$ there exists $n \in \mathbb {N}$ $n \in N$ such that any 3-connected graph G with $v(G) \ge n$ $v (G) \geq n$ has a k-vertex contractible set. It is proved that this holds if $k \ge 5$ $k \geq 5$ and $\delta (G) \ge \left[ \frac{2k + 1}{3} \right] + 2$ $δ (G) \geq [\frac{2 k + 1}{3}] + 2$ . Bibliography: 9 titles.