Geodesic
Dot product representations of planar graphs
The electronic journal of combinatorics, Tome 18 (2011) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

A graph $G$ is a $k$-dot product graph if there exists a vector labelling $u: V(G) \to \mathbb{R}^k$ such that $u(i)^{T}u(j) \geq 1$ if and only if $ij \in 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.
DOI : 10.37236/703
Classification : 05C62 
@article{10_37236_703,
     author = {Ross J. Kang and L\'aszl\'o Lov\'asz and Tobias M\"uller and Edward R. Scheinerman},
     title = {Dot product representations of planar graphs},
     journal = {The electronic journal of combinatorics},
     year = {2011},
     volume = {18},
     number = {1},
     doi = {10.37236/703},
     zbl = {1230.05218},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/703/}
}
TY  - JOUR
AU  - Ross J. Kang
AU  - László Lovász
AU  - Tobias Müller
AU  - Edward R. Scheinerman
TI  - Dot product representations of planar graphs
JO  - The electronic journal of combinatorics
PY  - 2011
VL  - 18
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/703/
DO  - 10.37236/703
ID  - 10_37236_703
ER  - 
%0 Journal Article
%A Ross J. Kang
%A László Lovász
%A Tobias Müller
%A Edward R. Scheinerman
%T Dot product representations of planar graphs
%J The electronic journal of combinatorics
%D 2011
%V 18
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/703/
%R 10.37236/703
%F 10_37236_703
Ross J. Kang; László Lovász; Tobias Müller; Edward R. Scheinerman. Dot product representations of planar graphs. The electronic journal of combinatorics, Tome 18 (2011) no. 1. doi: 10.37236/703

Cité par Sources :