×

Minimally triangle-saturated graphs: Adjoining a single vertex. (English) Zbl 0991.05058

A (finite, simple) graph is called triangle-saturated if adding any edge produces at least one new triangle (3-cycle). Using properties of dominating sets of vertices of a triangle-saturated graph \(G\), the authors investigate conditions under which a single vertex can be added to \(G\) so as to obtain a new triangle-saturated graph, and, in particular, conditions under which this extension is minimally saturated and primitive. The construction is applied to produce a family of primitive maximal triangle-free graphs, showing that the number of such graphs grows at least linearly with the number of vertices (while the growth rate is conjectured to be exponential).

MSC:

05C35 Extremal problems in graph theory
05C38 Paths and cycles
PDFBibTeX XMLCite