Bicliques and eigenvalues

Authors
Haemers, WH
Citation
Wh. Haemers, Bicliques and eigenvalues, J COMB TH B, 82(1), 2001, pp. 56-66
Citations number
11
Categorie Soggetti
Mathematics
Journal title
JOURNAL OF COMBINATORIAL THEORY SERIES B
ISSN journal
00958956 → ACNP
Volume
82
Issue
1
Year of publication
2001
Pages
56 - 66
Database
ISI
SICI code
0095-8956(200103)82:1<56:BAE>2.0.ZU;2-L
Abstract
A biclique in a graph Gamma is a complete bipartite subgraph of Gamma. We g ive bounds for the maximum number of edges in a biclique in terms of the ei genvalues of matrix representations of Gamma. These bounds show a strong si milarity with Lovasz's bound theta(Gamma) for the Shannon capacity of Gamma . Motivated by this similarity we investigate bicliques and the bounds in c ertain product graphs. (C) 2001 Academic Press.