Abstract
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 language | English (US) |
---|---|
Pages (from-to) | 647-655 |
Number of pages | 9 |
Journal | Graphs and Combinatorics |
Volume | 25 |
Issue number | 5 |
DOIs | |
State | Published - Feb 2010 |
Keywords
- Graph representation
- Random graphs
- Trace of hypergraphs
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics