Skip to content
DraconiticResearch
Search Sources API
197,768 studies31 sourcesUpdated 56 min ago
PreprintarXiv licencearXiv

On extending induced subgraphs

  • Guoli Ding
  • Jake Weber
  • Weihao Xia
Open at sourcePDFDOICite

Abstract

When characterizing graphs defined by forbidden induced subgraphs, it is often desirable to understand how a graph G can be generated incrementally from a given induced subgraph H. In this paper, we study a number of problems within this framework. First, for several notions of connectivity, we determine all minimal induced subgraphs of G that contain H and attain the connectivity of G. Second, we establish how to grow H inside G while preserving twin-freeness and certain forms of connectivity. Third, we establish {\it finite test theorems} for various graph classes, proving that agreement with the recursively generated graphs for a few initial iterations forces agreement at all subsequent iterations. Consequently, such an infinite graph family can be completely determined by finitely many of its initial generations. As an application, we characterize {๐•ƒ1,๐•ƒ3}-free graphs, where ๐•ƒ1 is the claw and ๐•ƒ3 is another forbidden graph for line graphs. Our structural results reduce this problem to a finite verification, which is completed through computer-assisted computation.

Related

  1. Large induced subgraphs with k vertices of maximum degree
    Zhen liu, Qinghou Zeng
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. A proof of Vince's conjecture on the average order of connected induced subgraphs
    Jungang Chen, Hongxia Ma
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. A Note on Vertex-Critical Induced Subgraphs of Shift Graphs
    Tomรกลก Kaiser, Matฤ›j Stehlรญk, Riste ล krekovski +1
    The Electronic Journal of CombinatoricsPeer-reviewedCC BY 4.0Full textCombinatorics & discrete mathematicsCrossref
  4. On the Minimum Possible Maximum Degree of Induced Subgraphs of Product Graphs
    Elizaveta Popova
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  5. Counting False-Twin Witnesses in Induced Subgraphs: An Exact Identity, a Two-Constraint Entropy Rate, and a Plateau
    Ali Nabavi, Rabih Ghostine
    MathematicsPeer-reviewedCC BY 4.0Combinatorics & discrete mathematicsCrossref

Cite

BibTeXRIS
BibTeX
@misc{ding2026extending,
  title = {{On extending induced subgraphs}},
  author = {Guoli Ding and Jake Weber and Weihao Xia},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.17598},
  eprint = {2610.17598},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.17598},
}
RIS
TY  - UNPB
TI  - On extending induced subgraphs
AU  - Guoli Ding
AU  - Jake Weber
AU  - Weihao Xia
PY  - 2026
DA  - 2026/10/13
PB  - arXiv
DO  - 10.48550/arxiv.2610.17598
UR  - https://arxiv.org/abs/2610.17598
AB  - When characterizing graphs defined by forbidden induced subgraphs, it is often desirable to understand how a graph G can be generated incrementally from a given induced subgraph H. In this paper, we study a number of problems within this framework. First, for several notions of connectivity, we determine all minimal induced subgraphs of G that contain H and attain the connectivity of G. Second, we establish how to grow H inside G while preserving twin-freeness and certain forms of connectivity. Third, we establish {\it finite test theorems} for various graph classes, proving that agreement with the recursively generated graphs for a few initial iterations forces agreement at all subsequent iterations. Consequently, such an infinite graph family can be completely determined by finitely many of its initial generations. As an application, we characterize {๐•ƒ_1,๐•ƒ_3}-free graphs, where ๐•ƒ_1 is the claw and ๐•ƒ_3 is another forbidden graph for line graphs. Our structural results reduce this problem to a finite verification, which is completed through computer-assisted computation.
ER  -