The Binding Number of a Graph and Its Cliques

Authors

Jeremy Lyle, University of Southern MississippiFollow
Wayne Goddard, Clemson UniversityFollow

Document Type

Article

Publication Date

8-6-2009

Department

Mathematics

School

Mathematics and Natural Sciences

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.

Comments

© 2009. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/.

Publication Title

Discrete Applied Mathematics

Volume

157

Issue

15

First Page

3336

Last Page

3340

Recommended Citation

Lyle, J., Goddard, W. (2009). The Binding Number of a Graph and Its Cliques. Discrete Applied Mathematics, 157(15), 3336-3340.
Available at: https://aquila.usm.edu/fac_pubs/1149