Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2603.11662 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912963138420736 |
|---|---|
| author | Liu, Haiyang Ning, Bo |
| author_facet | Liu, Haiyang Ning, Bo |
| contents | We prove that any \(2\)-connected graph \(G\) on \(n\) vertices with minimum degree \(δ(G) \ge \frac{n}{4}+2\) contains a \(2\)-connected subgraph of order \(k\) for every integer \(k\) with \(4 \le k \le n\). This improves a previous result of Yin and Wu. In \cite{YinWu-DAM-2026}, Yin and Wu proposed two conjectures. The first states that for any \(2\)-connected graph \(G\) of order \(n\) and size \(m\), there exists a \(2\)-connected subgraph of order \(k\) for each \(k \in \{4, \dots, n\}\) whenever \(m \ge \frac{1}{2} n^{3/2}\). The second conjecture asserts that the same conclusion holds under the alternative condition \(δ(G) \ge \sqrt{n}\). In this paper, we construct counterexamples that completely disprove the first conjecture. Furthermore, using the existence of \((v, k, 2)\)-Symmetric Balanced Incomplete Block designs (i.e., SBIBDs), we disprove the second conjecture for all \(n \in \{8, 14, 22, 32, 74, 112, 158\}\). Finally, we propose a conjecture of our own: for any \(2\)-connected graph \(G\) on \(n\) vertices with \(δ(G) \ge \frac{n}{k}\), where \(k \ge 3\) and \(n\) is sufficiently large, \(G\) contains a \(2\)-connected subgraph of every order from \(4\) to \(n\). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_11662 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | An Improved Interpolation Theorem and Disproofs of Two Conjectures on 2-Connected Subgraphs Liu, Haiyang Ning, Bo Combinatorics We prove that any \(2\)-connected graph \(G\) on \(n\) vertices with minimum degree \(δ(G) \ge \frac{n}{4}+2\) contains a \(2\)-connected subgraph of order \(k\) for every integer \(k\) with \(4 \le k \le n\). This improves a previous result of Yin and Wu. In \cite{YinWu-DAM-2026}, Yin and Wu proposed two conjectures. The first states that for any \(2\)-connected graph \(G\) of order \(n\) and size \(m\), there exists a \(2\)-connected subgraph of order \(k\) for each \(k \in \{4, \dots, n\}\) whenever \(m \ge \frac{1}{2} n^{3/2}\). The second conjecture asserts that the same conclusion holds under the alternative condition \(δ(G) \ge \sqrt{n}\). In this paper, we construct counterexamples that completely disprove the first conjecture. Furthermore, using the existence of \((v, k, 2)\)-Symmetric Balanced Incomplete Block designs (i.e., SBIBDs), we disprove the second conjecture for all \(n \in \{8, 14, 22, 32, 74, 112, 158\}\). Finally, we propose a conjecture of our own: for any \(2\)-connected graph \(G\) on \(n\) vertices with \(δ(G) \ge \frac{n}{k}\), where \(k \ge 3\) and \(n\) is sufficiently large, \(G\) contains a \(2\)-connected subgraph of every order from \(4\) to \(n\). |
| title | An Improved Interpolation Theorem and Disproofs of Two Conjectures on 2-Connected Subgraphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2603.11662 |