Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. Two notions of unit distance graphs
 
research article

Two notions of unit distance graphs

Alon, Noga
•
Kupavskii, Andrey  
2014
Journal Of Combinatorial Theory Series A

A faithful (unit) distance graph in R-d is a graph whose set of vertices is a finite subset of the d-dimensional Euclidean space, where two vertices are adjacent if and only if the Euclidean distance between them is exactly 1. A (unit) distance graph in Rd is any subgraph of such a graph. In the first part of the paper we focus on the differences between these two classes of graphs. In particular, we show that for any fixed d the number of faithful distance graphs in Rd on n labelled vertices is 2((1+o(1))dn log2 n), and give a short proof of the known fact that the number of distance graphs in Rd on n labelled vertices is 2((1-1/left perpendiculard/2right perpendicular + o(1))n2/2.) We also study the behavior of several Ramsey-type quantities involving these graphs. In the second part of the paper we discuss the problem of determining the minimum possible number of edges of a graph which is not isomorphic to a faithful distance graph in R-d. (C) 2014 Elsevier Inc. All rights reserved.

  • Details
  • Metrics
Type
research article
DOI
10.1016/j.jcta.2014.02.006
Web of Science ID

WOS:000336559900001

Author(s)
Alon, Noga
Kupavskii, Andrey  
Date Issued

2014

Publisher

Academic Press Inc Elsevier Science

Published in
Journal Of Combinatorial Theory Series A
Volume

125

Start page

1

End page

17

Subjects

Unit distance graph

•

Graph representation

•

Graph dimension

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
DCG  
Available on Infoscience
August 29, 2014
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/106398
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés