Minimum difference representations of graphs

József Balogh; Noah Prince

doi:10.1007/s00373-010-0875-3

Minimum difference representations of graphs

József Balogh, Noah Prince

Mathematics

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

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 n₀ such that for n > n₀ '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	https://doi.org/10.1007/s00373-010-0875-3
State	Published - Feb 2010

Keywords

Graph representation
Random graphs
Trace of hypergraphs

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Online availability

10.1007/s00373-010-0875-3

Library availability

Discover UIUC Full Text

Cite this

@article{18033d1b7395420e9df3e8598bf9febb,

title = "Minimum difference representations of graphs",

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.",

keywords = "Graph representation, Random graphs, Trace of hypergraphs",

author = "J{\'o}zsef Balogh and Noah Prince",

note = "Research supported in part by NSF grants DMS-0302804, DMS-0603769 and DMS-0600303, UIUC Campus Research Board 06139 and 07048, and OTKA 049398. Research supported in part by UIUC Campus Research Board 07048.",

year = "2010",

month = feb,

doi = "10.1007/s00373-010-0875-3",

language = "English (US)",

volume = "25",

pages = "647--655",

journal = "Graphs and Combinatorics",

issn = "0911-0119",

publisher = "Springer Japan",

number = "5",

}

TY - JOUR

T1 - Minimum difference representations of graphs

AU - Balogh, József

AU - Prince, Noah

N1 - Research supported in part by NSF grants DMS-0302804, DMS-0603769 and DMS-0600303, UIUC Campus Research Board 06139 and 07048, and OTKA 049398. Research supported in part by UIUC Campus Research Board 07048.

PY - 2010/2

Y1 - 2010/2

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

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

KW - Graph representation

KW - Random graphs

KW - Trace of hypergraphs

UR - http://www.scopus.com/inward/record.url?scp=77949425196&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77949425196&partnerID=8YFLogxK

U2 - 10.1007/s00373-010-0875-3

DO - 10.1007/s00373-010-0875-3

M3 - Article

AN - SCOPUS:77949425196

SN - 0911-0119

VL - 25

SP - 647

EP - 655

JO - Graphs and Combinatorics

JF - Graphs and Combinatorics

IS - 5

ER -

Minimum difference representations of graphs

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this