Minimum net-saturated graphs of even order

Let \(F\) be the net, consisting of a triangle with one distinct degree-one vertex attached to each of its vertices. A graph is \(F\)-saturated if it contains no copy of \(F\), but adding any missing edge creates one. Zhao, You and Zhang determined the minimum number of edges and conjectured that the minimum graph is unique at every sufficiently large even order. We prove that for every even \(n\ge12\), there are exactly four minimum \(n\)-vertex \(F\)-saturated graphs up to isomorphism, each with \(3n/2\) edges. Three additional families therefore disprove their even-order uniqueness conjecture. Two have no universal vertex, that is, no vertex adjacent to every other vertex. We also construct a ten-vertex minimum graph with fifteen edges outside the four families, proving that the threshold twelve is optimal. The key structural step forces a pendant triangle, meaning a triangle with two vertices of degree two, in every even-order minimum graph above order ten. We classify the graphs containing such a triangle and bound the order of all remaining extremal configurations by ten.

Authors

Publication Details

Journal
arXiv (Cornell University)
Published
2026-11-02
DOI
https://doi.org/10.48550/arxiv.2611.02399
Primary Topic
Limits and Structures in Graph Theory
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
preprint

Minimum net-saturated graphs of even order

Xuanyu Cao, Chunxiang Wang
arXiv (Cornell University)
Limits and Structures in Graph Theory
preprint

Minimum net-saturated graphs of even order

Xuanyu Cao, Chunxiang Wang
preprint en

Abstract

Let \(F\) be the net, consisting of a triangle with one distinct degree-one vertex attached to each of its vertices. A graph is \(F\)-saturated if it contains no copy of \(F\), but adding any missing edge creates one. Zhao, You and Zhang determined the minimum number of edges and conjectured that the minimum graph is unique at every sufficiently large even order. We prove that for every even \(n\ge12\), there are exactly four minimum \(n\)-vertex \(F\)-saturated graphs up to isomorphism, each with \(3n/2\) edges. Three additional families therefore disprove their even-order uniqueness conjecture. Two have no universal vertex, that is, no vertex adjacent to every other vertex. We also construct a ten-vertex minimum graph with fifteen edges outside the four families, proving that the threshold twelve is optimal. The key structural step forces a pendant triangle, meaning a triangle with two vertices of degree two, in every even-order minimum graph above order ten. We classify the graphs containing such a triangle and bound the order of all remaining extremal configurations by ten.

arXiv (Cornell University)
Limits and Structures in Graph Theory
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon
Minimum net-saturated graphs of even order — Xuanyu Cao, Chunxiang Wang · arXiv (Cornell University) (2026) | TGRS Research Map | TGRS