Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 31 min ago
PreprintarXiv licencearXiv

Contractable 2-connected subgraphs in minimally 3-connected graphs

  • Rongchuan Tao
Open at sourcePDFDOICite

Abstract

We study the 2-connected subgraphs of minimally 3-connected graphs whose contraction preserves 3-connectedness. We show that every minimally 3-connected graph that is not a wheel or a complete bipartite graph K3,n contains a contractable 2-connected induced subgraph that is a cycle, a fan, a K2,n or a K3,n. In addition, these subgraphs satisfy certain degree restrictions. We show that none of these four families can be discarded since for each one of the four families, there exists a minimally 3-connected graph containing a contractable induced 2-connected subgraph in that family and none in the other three families. Reversing the contraction process gives a new construction for 3-connected graphs using edge addition, expansions into prescribed 2-connected subgraphs and Y-sum.

Related

  1. A proof of Vince's conjecture on the average order of connected induced subgraphs
    Jungang Chen, Hongxia Ma
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. A Sublinear Minimum-Degree Condition for $2$-Connected Subgraphs of All Orders
    Kenta Ozeki, Takahiro Ueoro
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. Sharp bounds for Duke--Erdős--Rödl problems on cycle-connected subgraphs
    Guorong Gao, Run Zhao
    arXivPreprintCC BY-NC-SA 4.0Full textCombinatorics & discrete mathematicsarXiv
  4. Sharp bounds and extremal structure of minimally strongly k-connected digraphs
    Junran Yu, Gregory Gutin, Hong-Jian Lai +1
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  5. Modulo k-orientations of highly edge-connected signed graphs
    You Lu, Zhengke Miao, Zhenyu Tian +1
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{tao2026contractable,
  title = {{Contractable 2-connected subgraphs in minimally 3-connected graphs}},
  author = {Rongchuan Tao},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2611.01588},
  eprint = {2611.01588},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.01588},
}
RIS
TY  - UNPB
TI  - Contractable 2-connected subgraphs in minimally 3-connected graphs
AU  - Rongchuan Tao
PY  - 2026
DA  - 2026/11/01
PB  - arXiv
DO  - 10.48550/arxiv.2611.01588
UR  - https://arxiv.org/abs/2611.01588
AB  - We study the 2-connected subgraphs of minimally 3-connected graphs whose contraction preserves 3-connectedness. We show that every minimally 3-connected graph that is not a wheel or a complete bipartite graph K_3,n contains a contractable 2-connected induced subgraph that is a cycle, a fan, a K_2,n or a K_3,n. In addition, these subgraphs satisfy certain degree restrictions. We show that none of these four families can be discarded since for each one of the four families, there exists a minimally 3-connected graph containing a contractable induced 2-connected subgraph in that family and none in the other three families. Reversing the contraction process gives a new construction for 3-connected graphs using edge addition, expansions into prescribed 2-connected subgraphs and Y-sum.
ER  -