Cycle-saturated graphs of minimum size (Q1916094): Difference between revisions
From MaRDI portal
Created a new Item |
Set OpenAlex properties. |
||
(5 intermediate revisions by 4 users not shown) | |||
Property / author | |||
Property / author: Q331395 / rank | |||
Property / author | |||
Property / author: Roger Entringer / rank | |||
Property / author | |||
Property / author: László A. Székely / rank | |||
Property / reviewed by | |||
Property / reviewed by: Miroslaw Truszczynski / rank | |||
Property / author | |||
Property / author: Lane H. Clark / rank | |||
Normal rank | |||
Property / author | |||
Property / author: Roger Entringer / rank | |||
Normal rank | |||
Property / author | |||
Property / author: László A. Székely / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Miroslaw Truszczynski / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On a Conjecture of Erdos, Hajnal and Moon / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5552097 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3852212 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4083484 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3781784 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Smallest maximally nonhamiltonian graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Smallest maximally nonhamiltonian graphs. II / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A Problem in Graph Theory / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Infinite Families of Nontrivial Trivalent Graphs Which are Not Tait Colorable / 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: Q4304346 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Asymptotic results on saturated graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3812267 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5750884 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5526641 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5554162 / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0012-365x(95)00173-t / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2006394242 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 09:39, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Cycle-saturated graphs of minimum size |
scientific article |
Statements
Cycle-saturated graphs of minimum size (English)
0 references
2 July 1996
0 references
Given a graph \(F\), a graph \(G\) is said to be \(F\)-saturated if \(F \nsubseteq G\) but \(F \subseteq G + e\) for every edge \(e\) in the complement of \(G\). For \(n \geq |V(F) |\), we define \(\text{sat} (n,F)\) to be the smallest size of an \(F\)-saturated graph of order \(n\). The paper presents a series of results that establish bounds on \(\text{sat} (n, C_k)\), where \(C_k\) stands for a cycle of length \(k\). It is shown that with the exceptions of \(k = 8\) and \(k = 10\), we have \(n + c_1 n/k \leq \text{sat} (n, C_k) \leq n + c_2 n/k\). Several more specific results are also presented.
0 references
saturated graphs
0 references
extremal problems
0 references
bounds
0 references
cycle
0 references