Note on induced subgraphs of the unit distance graphE
n |
| |
Authors: | Hiroshi Maehara |
| |
Institution: | (1) Ryukyu University, Nishihara, Okinawa, Japan |
| |
Abstract: | The unit distance graphE
n
is the graph whose vertices are the points in Euclideann-space, and two vertices are adjacent if and only if the distance between them is 1. We prove that for anyn there is a finite bipartite graph which cannot be embedded inE
n
as an induced subgraph and that every finite graph with maximum degreed can be embedded inE
N
,N=(d
3 –d)/2, as an induced subgraph. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|