Covering graphs by the minimum number of equivalence relations

Research output: Contribution to journalArticle

37 Scopus citations

Abstract

An equivalence graph is a vertex disjoint union of complete graphs. For a graph G, let eq(G) be the minimum number of equivalence subgraphs of G needed to cover all edges of G. Similarly, let cc(G) be the minimum number of complete subgraphs of G needed to cover all its edges. Let H be a graph on n vertices with maximal degree ≦d (and minimal degree ≧1), and let G= {Mathematical expression} be its complement. We show that {Mathematical expression} The lower bound is proved by multilinear techniques (exterior algebra), and its assertion for the complement of an n-cycle settles a problem of Frankl. The upper bound is proved by probabilistic arguments, and it generalizes results of de Caen, Gregory and Pullman.

Original languageEnglish (US)
Pages (from-to)201-206
Number of pages6
JournalCombinatorica
Volume6
Issue number3
DOIs
StatePublished - Sep 1 1986
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics

Keywords

  • AMS subject classification (1980): 68E10, 68E05, 05B25, 05C55

Fingerprint Dive into the research topics of 'Covering graphs by the minimum number of equivalence relations'. Together they form a unique fingerprint.

  • Cite this