Title

The Binding Number of a Graph and Its Cliques

Document Type

Article

Publication Date

8-6-2009

Department

Mathematics

Abstract

We consider the binding numbers of K(r)-free graphs, and improve the upper bounds on the binding number which force a graph to contain a clique of order r. For the case r = 4, we provide a construction for K(4)-free graphs which have a larger binding number than the previously known constructions. This leads to a counterexample to a conjecture by Caro regarding the neighborhoods of independent sets. (C) 2009 Elsevier B.V. All rights reserved.

Publication Title

Discrete Applied Mathematics

Volume

157

Issue

15

First Page

3336

Last Page

3340