A Note on Cliques and Independent Sets

Roger C. Entringer; Wayne Goddard; Michael A. Henning

doi:10.1002/(SICI)1097-0118(199701)24:1<21::AID-JGT3>3.0.CO;2-L

A Note on Cliques and Independent Sets

Roger C. Entringer
, Wayne Goddard
, Michael A. Henning

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

15 Citations (Scopus)

Abstract

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)²].

Original language	English
Pages (from-to)	21-23
Number of pages	3
Journal	Journal of Graph Theory
Volume	24
Issue number	1
DOIs	https://doi.org/10.1002/(SICI)1097-0118(199701)24:1<21::AID-JGT3>3.0.CO;2-L
Publication status	Published - Jan 1997
Externally published	Yes

ASJC Scopus subject areas

Geometry and Topology

Access to Document

10.1002/(SICI)1097-0118(199701)24:1<21::AID-JGT3>3.0.CO;2-L

Cite this

@article{2a10dfe2a3af4a08ba7e70ac08171739,

title = "A Note on Cliques and Independent Sets",

abstract = "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].",

author = "Entringer, \{Roger C.\} and Wayne Goddard and Henning, \{Michael A.\}",

year = "1997",

month = jan,

doi = "10.1002/(SICI)1097-0118(199701)24:1<21::AID-JGT3>3.0.CO;2-L",

language = "English",

volume = "24",

pages = "21--23",

journal = "Journal of Graph Theory",

issn = "0364-9024",

publisher = "Wiley-Liss Inc.",

number = "1",

}

TY - JOUR

T1 - A Note on Cliques and Independent Sets

AU - Entringer, Roger C.

AU - Goddard, Wayne

AU - Henning, Michael A.

PY - 1997/1

Y1 - 1997/1

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

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

UR - https://www.scopus.com/pages/publications/0031543134

U2 - 10.1002/(SICI)1097-0118(199701)24:1<21::AID-JGT3>3.0.CO;2-L

DO - 10.1002/(SICI)1097-0118(199701)24:1<21::AID-JGT3>3.0.CO;2-L

M3 - Article

AN - SCOPUS:0031543134

SN - 0364-9024

VL - 24

SP - 21

EP - 23

JO - Journal of Graph Theory

JF - Journal of Graph Theory

IS - 1

ER -

A Note on Cliques and Independent Sets

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this