Redundant Trees in Bipartite Graphs
It has been conjectured that for each positive integer <i>k</i> and each tree <i>T</i> with bipartite <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>(</mo><msub&...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2025-03-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/13/6/1005 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | It has been conjectured that for each positive integer <i>k</i> and each tree <i>T</i> with bipartite <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>(</mo><msub><mi>Z</mi><mn>1</mn></msub><mo>,</mo><msub><mi>Z</mi><mn>2</mn></msub><mo>)</mo></mrow></semantics></math></inline-formula>, every <i>k</i>-connected bipartite graph <i>G</i> with <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>δ</mi><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow><mo>≥</mo><mi>k</mi><mo>+</mo><mo movablelimits="true" form="prefix">max</mo><mo>{</mo><mo>|</mo><msub><mi>Z</mi><mn>1</mn></msub><mo>|</mo><mo>,</mo><mo>|</mo><msub><mi>Z</mi><mn>2</mn></msub><mo>|</mo><mo>}</mo></mrow></semantics></math></inline-formula> admits a subgraph <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msup><mi>T</mi><mo>′</mo></msup><mo>≅</mo><mi>T</mi></mrow></semantics></math></inline-formula> such that <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>G</mi><mo>−</mo><mi>V</mi><mo>(</mo><msup><mi>T</mi><mo>′</mo></msup><mo>)</mo></mrow></semantics></math></inline-formula> is still <i>k</i>-connected. In this paper, we generalize the ear decompositions of 2-connected graphs into a <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>(</mo><mi>k</mi><mo>,</mo><msub><mi>a</mi><mi>k</mi></msub><mo>)</mo></mrow></semantics></math></inline-formula>-extensible system for a general <i>k</i>-connected graph. As a result, we confirm the conjecture for <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>k</mi><mo>≤</mo><mn>3</mn></mrow></semantics></math></inline-formula> by proving a slightly stronger version of it. |
|---|---|
| ISSN: | 2227-7390 |