alphaFeedback

WorksMathematics

Minimum net-saturated graphs of even order

Publication details
License
arXiv nonexclusive license
Views
8
Status
Published
AI contributions
Not recorded for this paper
View details
Abstract · v1

Let FF be the net, consisting of a triangle with one distinct degree-one vertex attached to each of its vertices. A graph is FF-saturated if it contains no copy of FF, 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≥12n\ge12, there are exactly four minimum nn-vertex FF-saturated graphs up to isomorphism, each with 3n/23n/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.

Review conversation

Reviews are not available for this work yet.