Minimum difference representations of graphs

József Balogh, Noah Prince

Research output: Contribution to journalArticlepeer-review


Define a k-minimum-difference-representation (k-MDR) of a graph G to be a family of sets {S(v): v ∈ V(G)} such that u and v are adjacent in G if and only if min{{pipe}S(u)-S(v){pipe}, {pipe}S(v)-S(u){pipe}} ≥ k. Define ρmin(G) to be the smallest k for which G has a k-MDR. In this note, we show that {ρmin(G)} is unbounded. In particular, we prove that for every k there is an n0 such that for n > n0 'almost all' graphs of order n satisfy ρmin(G) > k. As our main tool, we prove a Ramsey-type result on traces of hypergraphs.

Original languageEnglish (US)
Pages (from-to)647-655
Number of pages9
JournalGraphs and Combinatorics
Issue number5
StatePublished - Feb 2010


  • Graph representation
  • Random graphs
  • Trace of hypergraphs

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Minimum difference representations of graphs'. Together they form a unique fingerprint.

Cite this