Minimum degree and the minimum size of \(K_2^t\)-saturated graphs (Q870972): Difference between revisions

A graph \(G\) is \(F\)-saturated if \(G\) contains no subgraph isomorphic to \(F\) but for any edge \(e \not\in G\), \(G + e\) contains \(F\). The minimum number of edges in a graph \(G\) of order \(n\) that is \(F\)-saturated is denoted by \(\text{sat}(n, F)\), and is denoted by \(\text{sat}(n, F, \delta)\) if only graphs \(G\) of minimum degree \(\delta\) are considered. It is shown for \(t \geq 3\) and \(n \geq 4t - 4\) that \(\text{sat}(n, K_2^t, 2t - 3) = \lceil ((4t - 5)n - 4t^2 + 6t - 1)/2 \rceil\), and \(\text{sat}(n, K_2^t) \geq \lceil ((4t - 5)n - 4t^2 + 6t - 1)/2 \rceil\), where \(K_2^t\) denotes the complete multipartite graph with \(t\) parts of size \(2\). It is conjectured there is equality if \(t \geq 3\) and \(n\) is sufficiently large.