Can I read Fragile Graphs with Small Independent Cuts on EtoBox?

Fragile Graphs with Small Independent Cuts by Guantao Chen; Ralph J. Faudree; Michael S. Jacobson is a Computer Science article available to read on EtoBox.

What is Fragile Graphs with Small Independent Cuts about?

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

Who reads Fragile Graphs with Small Independent Cuts?

Author

Guantao Chen; Ralph J. Faudree; Michael S. Jacobson

Publisher

John Wiley and Sons; Wiley (John Wiley & Sons); John Wiley & Sons Inc.; Wiley (ISSN 0364-9024)

Published

2002

Language

EN

Field

Computer Science (Physical Sciences)