𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Minimum C5-saturated graphs

✍ Scribed by Ya-Chen Chen

Publisher
John Wiley and Sons
Year
2009
Tongue
English
Weight
208 KB
Volume
61
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

A graph is C~5~‐saturated if it has no five‐cycle as a subgraph, but does contain a C~5~ after the addition of any new edge. We prove that the minimum number of edges in a C~5~ ‐saturated graph on n≥11 vertices is sat(n, C~5~)=⌈10(n−1)/7⌉−1 if n∈N~0~={11, 12, 13, 14, 16, 18, 20} and is ⌈10(n−1)/7⌉ if n≥11 and n∉N~0~. © 2009 Wiley Periodicals, Inc. J Graph Theory

📜 SIMILAR VOLUMES

Cycle-saturated graphs of minimum size
Cycle-saturated graphs of minimum size
✍ C.A. Barefoot; L.H. Clark; R.C. Entringer; T.D. Porter; L.A. Székely; Zs. Tuza 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 707 KB

A graph G is called Ck-saturated if G contains no cycles of length k but does contain such a cycle after the addition of any new edge. Bounds are obtained for the minimum number of edges in Ck-saturated graphs for all k ~ 8 or 10 and n sufficiently large. In general, it is shown that the minimum is

Detour-saturated graphs
Detour-saturated graphs
✍ Lowell W. Beineke; J. E. Dunbar; M. Frick 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 160 KB

## Abstract A graph is said to be detour‐saturated if the addition of any edge results in an increased greatest path length. In this paper, we add to the relatively small amount that is known about detour‐saturated graphs. Our main result is a determination of all connected detour‐saturated graphs

Edge-colored saturated graphs
Edge-colored saturated graphs
✍ D. Hanson; B. Toft 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 266 KB
Conditional diameter saturated graphs
Conditional diameter saturated graphs
✍ C. Balbuena; P. García-Vázquez; X. Marcote; J.C. Valenzuela 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 115 KB

## Abstract The conditional diameter __D__~__𝒫__~(__G__) of a connected graph __G__ is a measure of the maximum distance between two subsets of vertices satisfying a given property __𝒫__ of interest. For any given integer __k__ ≥ 1, a connected graph __G__ is said to be conditional diameter __k__‐s