Dot product representations of planar graphs

Ross J. Kang; László Lovász; Tobias Müller; Edward R. Scheinerman

Dot product representations of planar graphs

Ross J. Kang, László Lovász, Tobias Müller, Edward R. Scheinerman

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

Abstract

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

Original language	English
Article number	P216
Number of pages	14
Journal	Electronic Journal of Combinatorics
Volume	18
Issue number	1
Publication status	Published - 2011
Externally published	Yes

Access to Document

http://www.combinatorics.org/ojs/index.php/eljc/article/view/v18i1p216

Cite this

@article{ef7969869b894f62863971a87de925db,

title = "Dot product representations of planar graphs",

abstract = "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∈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.",

author = "Kang, {Ross J.} and L{\'a}szl{\'o} Lov{\'a}sz and Tobias M{\"u}ller and Scheinerman, {Edward R.}",

year = "2011",

language = "English",

volume = "18",

journal = "Electronic Journal of Combinatorics",

issn = "1077-8926",

publisher = "Electronic Journal of Combinatorics",

number = "1",

}

TY - JOUR

T1 - Dot product representations of planar graphs

AU - Kang, Ross J.

AU - Lovász, László

AU - Müller, Tobias

AU - Scheinerman, Edward R.

PY - 2011

Y1 - 2011

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

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

M3 - Article

SN - 1077-8926

VL - 18

JO - Electronic Journal of Combinatorics

JF - Electronic Journal of Combinatorics

IS - 1

M1 - P216

ER -

Dot product representations of planar graphs

Abstract

Access to Document

Fingerprint

Cite this