Abstract
For integers m, n ≥ 2, let g(m, n) be the minimum order of a graph, where every vertex belongs to both a clique Km of order m and a biclique K(n, n). We show that g(m, n) = 2(m + n - 2) if m ≤ n-2. Furthermore, for m ≥ n - 1, we establish that g(m, n) = [(√m - 1 + √n - 1)2] if [√(m - 1)(n - 1)] ≡ 0 mod(n - 1) or, if m is sufficiently large and √(m - 1)(n - 1) is not an integer.
| Original language | English |
|---|---|
| Pages (from-to) | 60-66 |
| Number of pages | 7 |
| Journal | Journal of Graph Theory |
| Volume | 34 |
| Issue number | 1 |
| DOIs | |
| Publication status | Published - May 2000 |
| Externally published | Yes |
Keywords
- Bicliques
- Cliques
- Homogeneous embeddings
ASJC Scopus subject areas
- Geometry and Topology