Premium
Fragile graphs with small independent cuts
Author(s) -
Chen Guantao,
Faudree Ralph J.,
Jacobson Michael S.
Publication year - 2002
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.10074
Subject(s) - combinatorics , mathematics , path graph , vertex (graph theory) , wheel graph , independent set , bound graph , discrete mathematics , graph , neighbourhood (mathematics) , graph power , line graph , mathematical analysis
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