<p>An edge <i>e</i> of a 3-connected graph <i>G</i> is <i>contractible</i> if <i>G</i>/<i>e</i> is 3-connected. A graph <i>G</i> is minimally 3-connected if <i>G</i> is 3-connected and for every <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2890_Article_IEq1.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="70" /> </InlineMediaObject> <EquationSource Format="TEX">\(e\in E(G)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>e</mi> <mo>∈</mo> <mi>E</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2890_Article_IEq2.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="33" /> </InlineMediaObject> <EquationSource Format="TEX">\(G \backslash e\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>G</mi> <mo stretchy="true">\</mo> <mi>e</mi> </mrow> </math></EquationSource> </InlineEquation> is not 3-connected. We show that if <i>G</i> is a minimally 3-connected graph, then every component of the graph spanned by all non-contractible edges is either a triangle or a star. Consequently, we obtain the following results on minimally 3-connected graphs. 1. If <i>G</i> has a spanning tree that contains no contractible edges, then <i>G</i> must be one of the wheel graphs. 2. Assume that <i>G</i> is not a wheel graph. If <i>G</i> has a spanning tree that contains exactly one contractible edge, then <i>G</i> belongs to one of the five infinitely classes of graphs; a precise structure is given for each class. 3. The number of contractible edges of <i>G</i> is at least the number of edges of <i>G</i> minus the number of degree 3 vertices. This bound is the best possible as shown by examples from the introduction section, thus improving other established bounds on the number of contractible edges.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Contractible Edges in Spanning Trees of 3-Connected Graphs

  • Chengfu Qin,
  • Jin Geng,
  • Hailing Yang,
  • Xiaoqing Xie

摘要

An edge e of a 3-connected graph G is contractible if G/e is 3-connected. A graph G is minimally 3-connected if G is 3-connected and for every \(e\in E(G)\) e E ( G ) , \(G \backslash e\) G \ e is not 3-connected. We show that if G is a minimally 3-connected graph, then every component of the graph spanned by all non-contractible edges is either a triangle or a star. Consequently, we obtain the following results on minimally 3-connected graphs. 1. If G has a spanning tree that contains no contractible edges, then G must be one of the wheel graphs. 2. Assume that G is not a wheel graph. If G has a spanning tree that contains exactly one contractible edge, then G belongs to one of the five infinitely classes of graphs; a precise structure is given for each class. 3. The number of contractible edges of G is at least the number of edges of G minus the number of degree 3 vertices. This bound is the best possible as shown by examples from the introduction section, thus improving other established bounds on the number of contractible edges.