✦ LIBER ✦

Cycle-saturated graphs of minimum size

✍ Scribed by C.A. Barefoot; L.H. Clark; R.C. Entringer; T.D. Porter; L.A. Székely; Zs. Tuza

Publisher: Elsevier Science
Year: 1996
Tongue: English
Weight: 707 KB
Volume: 150
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(95)00173-t

No coin nor oath required. For personal study only.

✦ Synopsis

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 between n + cln/k and n + c2n/k for some positive constants cl and c2. Our results provide an asymptotic solution to a 15-year-old problem of Bollob~,s.

📜 SIMILAR VOLUMES

Minimum C5-saturated graphs

✍ Ya-Chen Chen 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 208 KB

## 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~=

Minimum cycle covers of graphs

✍ Fan, Genghua 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 145 KB 👁 1 views

Some new results on minimum cycle covers are proved. As a consequence, it is obtained that the edges of a bridgeless graph G can be covered by cycles of total length at most |E(G)| + 25 24 (|V (G)| -1), and at most |E(G)| + |V (G)| -1 if G contains no circuit of length 8 or 12.

All minimum C5-saturated graphs

✍ Ya-Chen Chen 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 234 KB

Minimum cycle bases of Halin graphs

✍ Peter F. Stadler 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 90 KB

## Abstract Halin graphs are planar 3‐connected graphs that consist of a tree and a cycle connecting the end vertices of the tree. It is shown that all Halin graphs that are not “necklaces” have a unique minimum cycle basis. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 150–155, 2003

On the minimum size of visibility graphs

✍ Alfredo Garcı&#x0301;a Olaverri; Ferran Hurtado; Marc Noy; Javier Tejel 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 177 KB

In this paper we give tight lower bounds on the size of the visibility graph, the contracted visibility graph, and the barvisibility graph of n disjoint line segments in the plane, according to their vertex-connectivity.

Minimum-weight cycles in 3-separable gra

Minimum-weight cycles in 3-separable graphs

✍ Coullard, Collette R.; Gardner, L. Leslie; Wagner, Donald K. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 136 KB 👁 2 views

This paper presents a polynomial-time algorithm for the minimum-weight-cycle problem on graphs that decompose via 3-separations into well-structured graphs. The problem is NP-hard in general. Graphs that decompose via 3-separations into well-structured graphs include Halin, outer-facial, deltawye, w