✦ LIBER ✦

On cliques and bicliques

✍ Scribed by Henning, Michael A.

Publisher: John Wiley and Sons
Year: 2000
Tongue: English
Weight: 97 KB
Volume: 34
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(200005)34:1<60::aid-jgt6>3.0.co;2-i

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 SIMILAR VOLUMES

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

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

Bicliques and Eigenvalues

✍ Willem H. Haemers 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 147 KB

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 simi

A note on cliques and independent sets

✍ Entringer, Roger C.; Goddard, Wayne; Henning, Michael A. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 58 KB 👁 2 views

For integers m, n ≥ 2, let f (m, n) be the minimum order of a graph where every vertex belongs to both a clique of cardinality m and an independent set of cardinality n. We show that f (m, n) = ( √ m -1 + √ n -1) 2 .

Another note on cliques and independent

Another note on cliques and independent sets

✍ Fred Galvin 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 50 KB 👁 2 views