𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Fragile graphs with small independent cuts

✍ Scribed by Guantao Chen; Ralph J. Faudree; Michael S. Jacobson

Publisher
John Wiley and Sons
Year
2002
Tongue
English
Weight
142 KB
Volume
41
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

A graph is called fragile if it has a vertex cut which is also an independent set. Chen and Yu proved that every graph with n vertices and at most 2__n__−4 edges is fragile, which was conjectured to be true by Caro. However, their proof does not give any information on the number of vertices in the independent cuts. The purpose of this paper is to investigate when a graph has a small independent cut. We show that if G is a graph on n vertices and at most (12__n__/7)−3 edges, then G contains an independent cut S with ∣S∣≤3. Upper bounds on the number of edges of a graph having an independent cut of size 1 or 2 are also obtained. We also show that for any positive integer k, there is a positive number ε such that there are infinitely many graphs G with n vertices and at most (2−ε)n edges, but G has no independent cut with less than k vertices. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 327–341, 2002

📜 SIMILAR VOLUMES

Graphs with small numbers of independent
Graphs with small numbers of independent edges
✍ Miroslav M. Petrović; Ivan Gutman; Mirko Lepović 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 327 KB

The graphs with exactly one, two or three independent edges are determined.

T-joins intersecting small edge-cuts in
T-joins intersecting small edge-cuts in graphs
✍ Tomáš Kaiser; Riste Škrekovski 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 130 KB

## Abstract In an earlier paper 3, we studied cycles in graphs that intersect all edge‐cuts of prescribed sizes. Passing to a more general setting, we examine the existence of __T__‐joins in grafts that intersect all edge‐cuts whose size is in a given set __A__ ⊆{1,2,3}. In particular, we character

Graphs with independent perfect matching
Graphs with independent perfect matchings
✍ Marcelo H. de Carvalho; Cláudio L. Lucchesi; U. S. R. Murty 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 241 KB

A graph with at least two vertices is matching covered if it is connected and each edge lies in some perfect matching. A matching covered graph G is extremal if the number of perfect matchings of G is equal to the dimension of the lattice spanned by the set of incidence

Coloring plane graphs with independent c
Coloring plane graphs with independent crossings
✍ Daniel Král'; Ladislav Stacho 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 268 KB

## Abstract We show that every plane graph with maximum face size four in which all faces of size four are vertex‐disjoint is cyclically 5‐colorable. This answers a question of Albertson whether graphs drawn in the plane with all crossings independent are 5‐colorable. © 2009 Wiley Periodicals, Inc.