Dot product representations of planar graphs

被引：0

作者：

Kang, Ross J. ^{[1
]}

Lovasz, Laszlo ^{[2
]}

Muller, Tobias

Scheinerman, Edward R.

机构：

[1] Univ Durham, Durham DH1 3HP, England

[2] Eotvos Lorand Univ, H-1364 Budapest, Hungary

来源：

ELECTRONIC JOURNAL OF COMBINATORICS | 2011年 / 18卷 / 01期

基金：

欧洲研究理事会; 英国工程与自然科学研究理事会;

关键词：

EUCLIDEAN SPACES; EMBEDDINGS;

D O I：

暂无

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

A graph G is a k-dot product graph if there exists a vector labelling u : V (G) -> R(k) such that u(i)(T)u(j) >= 1 if and only if ij is an element of E(G). Fiduccia, Scheinerman, Trenk and Zito [Discrete Math., 1998] asked whether every planar graph is a 3-dot product graph. We show that the answer is "no". On the other hand, every planar graph is a 4-dot product graph. We also answer the corresponding questions for planar graphs of prescribed girth and for outerplanar graphs.

引用

页数：14