✦ LIBER ✦

A note on cliques and independent sets

✍ Scribed by Entringer, Roger C.; Goddard, Wayne; Henning, Michael A.

Publisher: John Wiley and Sons
Year: 1997
Tongue: English
Weight: 58 KB
Volume: 24
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199701)24:1<21::aid-jgt3>3.0.co;2-l

No coin nor oath required. For personal study only.

✦ Synopsis

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 .

📜 SIMILAR VOLUMES

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

On hitting all maximum cliques with an i

On hitting all maximum cliques with an independent set

✍ Landon Rabern 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 77 KB

A Note on Difference Sets

✍ Hikoe Enomoto; Mariko Hagita; Makoto Matsumoto 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 234 KB

Let D be a (v, k, \*)-difference set in a group G. Assume that G has a normal subgroup N such that GÂN is cyclic or nearly cyclic. Under the self-conjugacy assumption on exp(GÂN), we shall give bounds on |N| and \*. The theorem is applicable to a wider variety of parameters for groups, not necessari

A note on cyclic difference sets

✍ Peter M. Neumann 📂 Article 📅 1974 🏛 John Wiley and Sons 🌐 English ⚖ 93 KB 👁 2 views

Hitting all maximum cliques with a stabl

Hitting all maximum cliques with a stable set using lopsided independent transversals

✍ Andrew D. King 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 82 KB

Rabern recently proved that any graph with ≥ 3 4 ( +1) contains a stable set meeting all maximum cliques. We strengthen this result, proving that such a stable set exists for any graph with > 2 3 ( +1). This is tight, i.e. the inequality in the statement must be strict. The proof relies on finding a

A note on orthogonal sets of hypercubes

✍ Anthony B. Evans 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 105 KB 👁 1 views

Mutually orthogonal sets of hypercubes are higher dimensional generalizations of mutually orthogonal sets of Latin squares. For Latin squares, it is well known that the Cayley table of a group of order n is a Latin square, which has no orthogonal mate if n is congruent to 2 modulo 4. We will prove a