Minimum net-saturated graphs of even order
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≥12, 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.
Related
- Minimum Weakly Saturated Graphs and Bootstrap Percolation in General Host Graphs
- On rainbow saturated graphs with minimum number of edges
- Graphs with Minimum Algebraic Connectivity II: Regular Graphs of Even Degree
- There are no nontrivial uniquely C_9-saturated graphs
- The saturated spectral radius for complete graphs
BibTeX
@misc{cao2026minimum,
title = {{Minimum net-saturated graphs of even order}},
author = {Xuanyu Cao and Chunxiang Wang},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.02399},
eprint = {2611.02399},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.02399},
}
RIS
TY - UNPB
TI - Minimum net-saturated graphs of even order
AU - Xuanyu Cao
AU - Chunxiang Wang
PY - 2026
DA - 2026/11/02
PB - arXiv
DO - 10.48550/arxiv.2611.02399
UR - https://arxiv.org/abs/2611.02399
AB - 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≥12, 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.
ER -