Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6871473 | Discrete Applied Mathematics | 2018 | 8 Pages |
Abstract
A graph G of order n satisfies the cut condition (CC) if there are at least |A| edges between any set AâV(G), |A|â¤nâ2, and its complement A¯=V(G)âA. For even n, G satisfies the even cut condition (ECC), if [A,A¯] contains at least nâ2 edges, for every AâV(G), |A|=nâ2. We investigate here the minimum number of edges in a graph G satisfying CC or ECC. A simple counting argument shows that for both cut conditions |E(G)|â¥nâ1, and the star K1,nâ1 is extremal. Faudree et al. (1999) conjectured that the extremal graphs with maximum degree Î(G)
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Adam S. Jobson, André E. Kézdy, JenÅ Lehel,