✦ LIBER ✦

Bicliques and Eigenvalues

✍ Scribed by Willem H. Haemers

Publisher: Elsevier Science
Year: 2001
Tongue: English
Weight: 147 KB
Volume: 82
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.2000.2020

No coin nor oath required. For personal study only.

✦ Synopsis

A biclique in a graph 1 is a complete bipartite subgraph of 1. We give bounds for the maximum number of edges in a biclique in terms of the eigenvalues of matrix representations of 1. These bounds show a strong similarity with Lova sz's bound (1) for the Shannon capacity of 1. Motivated by this similarity we investigate bicliques and the bounds in certain product graphs.

📜 SIMILAR VOLUMES

Biclique graphs and biclique matrices

✍ Marina Groshaus; Jayme L. Szwarcfiter 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 203 KB

## Abstract A biclique of a graph __G__ is a maximal induced complete bipartite subgraph of __G__. Given a graph __G__, the biclique matrix of __G__ is a {0,1,−1} matrix having one row for each biclique and one column for each vertex of __G__, and such that a pair of 1, −1 entries in a same row cor

On cliques and bicliques

✍ Henning, Michael A. 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 97 KB 👁 1 views

For integers m, n ≥ 2, let g(m, n) be the minimum order of a graph, where every vertex belongs to both a clique K m of order m and a biclique K(n, n). or, if m is sufficiently large and (m -1)(n -1) is not an integer.

Approximating Clique and Biclique Proble

Approximating Clique and Biclique Problems

✍ Dorit S. Hochbaum 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 317 KB

We present here 2-approximation algorithms for several node deletion and edge deletion biclique problems and for an edge deletion clique problem. The biclique problem is to find a node induced subgraph that is bipartite and complete. The objective is to minimize the total weight of nodes or edges de

Covering cliques with spanning bicliques

✍ K�ndgen, Andr� 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 192 KB

The edges of the complete graph on n vertices can be covered by lg n spanning complete bipartite subgraphs. However, the sum of the number of edges in these subgraphs is roughly (n 2 /4)lg n, while a cover consisting of n -1 spanning stars uses only (n -1) 2 edges. We will show that the covering by

Rank and biclique partitions of the comp

Rank and biclique partitions of the complement of paths

✍ Boyer, Elizabeth D. 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 230 KB 👁 1 views

The problem was posed of determining the biclique partition number of the complement of a Hamiltonian path (Monson, Rees, and Pullman, Bull. Inst. Combinatorics and Appl. 14 (1995), 17-86). We define the complement of a path P , denoted P , as the complement of P in K m,n where P is a subgraph of K

Maxwell and Lamé eigenvalues on polyhedr

Maxwell and Lamé eigenvalues on polyhedra

✍ Martin Costabel; Monique Dauge 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 249 KB

In a convex polyhedron, a part of the Lame´eigenvalues with hard simple support boundary conditions does not depend on the Lame´coefficients and coincides with the Maxwell eigenvalues. The other eigenvalues depend linearly on a parameter s linked to the Lame´coefficients and the associated eigenmode