Cycle-saturated graphs of minimum size
type: Item
instance of: scholarly article
title: Cycle-saturated graphs of minimum size
zbMATH Open document ID: 0856.05058
DOI: 10.1016/0012-365X(95)00173-T
author: Curtiss Barefoot
author: Thom Porter
author: Zsolt Tuza
author: Lane Clark
author: R. C. Entringer
author: László A. Székely
published in: Discrete Mathematics
publication date: 1996-07-02T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 895985
zbMATH Keywords: saturated graphs
zbMATH Keywords: extremal problems
zbMATH Keywords: bounds
zbMATH Keywords: cycle
reviewed by: Mirosław Truszczyński
MaRDI profile type: Publication
cites work: On a Conjecture of Erdos, Hajnal and Moon
cites work: Q5552097
cites work: Q3852212
cites work: Q4083484
cites work: Q3781784
cites work: Smallest maximally nonhamiltonian graphs
cites work: Smallest maximally nonhamiltonian graphs. II
cites work: A Problem in Graph Theory
cites work: Infinite Families of Nontrivial Trivalent Graphs Which are Not Tait Colorable
cites work: Saturated graphs with minimal number of edges
cites work: Q5678889
cites work: Q4304346
cites work: Asymptotic results on saturated graphs
cites work: Q3812267
cites work: Q5750884
cites work: Q5526641
cites work: Q5554162
full work available at URL: 0012-365x(95)00173-t
OpenAlex ID: W2006394242
Recommended article: Cycle-Saturated Graphs with Minimum Number of Edges
Recommended article: Constructive upper bounds for cycle-saturated graphs of minimum size
Recommended article: Minimum \(C_k\)-saturated graphs
Recommended article: Cycle lengths and minimum degree of graphs
Recommended article: Q3483303
Recommended article: Q4344209
Recommended article: Minimizing the numbers of cliques and cycles of fixed size in an \(F\)-saturated graph
Recommended article: Q4949780
Recommended article: Saturated Graphs of Prescribed Minimum Degree
description: scientific article; zbMATH DE number 895985