On cliques and bicliques

Michael A. Henning

doi:10.1002/(SICI)1097-0118(200005)34:1<60::AID-JGT6>3.0.CO;2-I

On cliques and bicliques

Michael A. Henning

University of KwaZulu-Natal

Research output: Contribution to journal › Article › peer-review

2 Citations (Scopus)

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 K_m 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)²] 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	https://doi.org/10.1002/(SICI)1097-0118(200005)34:1<60::AID-JGT6>3.0.CO;2-I
Publication status	Published - May 2000
Externally published	Yes

Keywords

Bicliques
Cliques
Homogeneous embeddings

ASJC Scopus subject areas

Geometry and Topology

Access to Document

10.1002/(SICI)1097-0118(200005)34:1<60::AID-JGT6>3.0.CO;2-I

Cite this

@article{81be069b89d7479d99326df206bf58a9,

title = "On cliques and bicliques",

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.",

keywords = "Bicliques, Cliques, Homogeneous embeddings",

author = "Henning, {Michael A.}",

year = "2000",

month = may,

doi = "10.1002/(SICI)1097-0118(200005)34:1<60::AID-JGT6>3.0.CO;2-I",

language = "English",

volume = "34",

pages = "60--66",

journal = "Journal of Graph Theory",

issn = "0364-9024",

publisher = "Wiley-Liss Inc.",

number = "1",

}

TY - JOUR

T1 - On cliques and bicliques

AU - Henning, Michael A.

PY - 2000/5

Y1 - 2000/5

N2 - 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.

AB - 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.

KW - Bicliques

KW - Cliques

KW - Homogeneous embeddings

UR - http://www.scopus.com/inward/record.url?scp=0034180083&partnerID=8YFLogxK

U2 - 10.1002/(SICI)1097-0118(200005)34:1<60::AID-JGT6>3.0.CO;2-I

DO - 10.1002/(SICI)1097-0118(200005)34:1<60::AID-JGT6>3.0.CO;2-I

M3 - Article

AN - SCOPUS:0034180083

SN - 0364-9024

VL - 34

SP - 60

EP - 66

JO - Journal of Graph Theory

JF - Journal of Graph Theory

IS - 1

ER -

On cliques and bicliques

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this