Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4651082 | Discrete Mathematics | 2007 | 6 Pages |
Abstract
In this paper we consider graphs which have no k vertex-disjoint cycles. For given integers k,αk,α let f(k,α)f(k,α) be the maximum order of a graph G with independence number α(G)⩽αα(G)⩽α, which has no k vertex-disjoint cycles. We prove that f(k,α)=3k+2α-3f(k,α)=3k+2α-3 if 1⩽α⩽51⩽α⩽5 or 1⩽k⩽21⩽k⩽2, and f(k,α)⩾3k+2α-3f(k,α)⩾3k+2α-3 in general. We also prove the following results: (1) there exists a constant cαcα (depending only on αα) such that f(k,α)⩽3k+cαf(k,α)⩽3k+cα, (2) there exists a constant tktk (depending only on k ) such that f(k,α)⩽2α+tkf(k,α)⩽2α+tk, and (3) there exists no absolute constant c such that f(k,α)⩽c(k+α)f(k,α)⩽c(k+α).
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Yoshimi Egawa, Hikoe Enomoto, Stanislav Jendrol, Katsuhiro Ota, Ingo Schiermeyer,