Minimum degree and the minimum size of \(K_2^t\)-saturated graphs (Q870972): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Q3852212 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4871771 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Minimalk-saturated and color critical graphs of prescribed minimum degree / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A Problem in Graph Theory / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Saturated graphs with minimal number of edges / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5678889 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The Minimum Size of Saturated Hypergraphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5750884 / rank | |||
Normal rank |
Latest revision as of 16:06, 25 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Minimum degree and the minimum size of \(K_2^t\)-saturated graphs |
scientific article |
Statements
Minimum degree and the minimum size of \(K_2^t\)-saturated graphs (English)
0 references
15 March 2007
0 references
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.
0 references
minimize size
0 references
complete multipartite graph
0 references