Two families of primitive minimally triangle-saturated graphs
James A. MacDougall, Roger B. Eggleton · 1996
The authors have previously shown [1] that to generate all triangle-saturated graphs (graphs of diameter at most 2), it su±ces to begin with the primitive minimally triangle-saturated graphs. In the present paper two infinite families of primitive minimally triangle-saturated graphs are constructed: one family covers all odd orders $n \geq 3$, the other all even orders $n \geq 4$, and in each case all graphs of order $n$ produced have the same size. For each order $n \geq 3$, the number of primitive minimally triangle-saturated graphs of order $n$ yielded by the relevant construction is exponentially quadratic in $n$.