全部 标题 作者
关键词 摘要

OALib Journal期刊
ISSN: 2333-9721
费用:99美元

查看量下载量

相关文章

更多...
Mathematics  2013 

Two notions of unit distance graphs

Full-Text   Cite this paper   Add to My Lib

Abstract:

A {\em faithful (unit) distance graph} in $\mathbb{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 {\em (unit) distance graph} in $\mathbb{R}^d$ 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 $\mathbb{R}^d$ on $n$ labelled vertices is $2^{(1+o(1)) d n \log_2 n}$, and give a short proof of the known fact that the number of distance graphs in $\mathbb{R}^d$ on $n$ labelled vertices is $2^{(1-1/\lfloor d/2 \rfloor +o(1))n^2/2}$. We also study the behavior of several Ramsey-type quantities involving these graphs. % and high-girth graphs from these classes. 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 $\mathbb R^d$.

Full-Text

Contact Us

service@oalib.com

QQ:3279437679

WhatsApp +8615387084133