Geometrical embeddings of graphs
type: Item
instance of: scholarly article
title: Geometrical embeddings of graphs
zbMATH Open document ID: 0684.05018
DOI: 10.1016/0012-365X(89)90142-8
published in: Discrete Mathematics
publication date: 1989-01-01T00:00:00Z
review text: First the paper considers generalized threshold graphs and gives a characterization of such graphs by a list of 11 forbidden induced subgraphs \((G_ 8\) being superfluous since it contains \(G_ 2\) as an induced subgraph). Then the scalar product dimension d(G) of a graph \(G=(V,E)\) is defined to be the minimum number d such that there exists a mapping f: \(V\to {\mathbb{R}}^ d\) and a threshold \(t\in {\mathbb{R}}\) with xy\(\in E\) iff f(x)f(y)\(\geq t\), where f(x)f(y) denotes the usual scalar product. Some general inequalities concerning d(G), the sphericity sph(G) and the spherical dimension sd(G) of a graph G are proved. Finally the authors determine the exact scalar product dimension of trees and of complements of cycles.
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 4120189
zbMATH Keywords: threshold dimension
zbMATH Keywords: distance dimension
zbMATH Keywords: generalized threshold graphs
zbMATH Keywords: forbidden induced subgraphs
zbMATH Keywords: sphericity
zbMATH Keywords: spherical dimension
zbMATH Keywords: scalar product dimension
zbMATH Keywords: trees
zbMATH Keywords: complements of cycles
author: Jan Reiterman
author: Vojtěch Rödl
author: Edita Šiňajová
reviewed by: Gerd Wegner
MaRDI profile type: Publication
cites work: On embedding triangle-free graphs in unit spheres
cites work: Q4165164
cites work: On the dimension of a graph
cites work: Q3918134
cites work: Embedding the n-cube in lower dimensions
cites work: Q3328583
cites work: A triangle free graph which cannot be \(\sqrt3\) imbedded in any Euclidean unit sphere
cites work: Q5530470
cites work: On the Shannon capacity of a graph
cites work: Space graphs and sphericity
cites work: Triangle free graphs that are not \(\sqrt{3}\)-embeddable in \(S^ n\).
cites work: On combinatorial properties of spheres in euclidean spaces
cites work: The Complexity of the Partial Order Dimension Problem
full work available at URL: 0012-365x(89)90142-8
OpenAlex ID: W2019029270
Recommended article: Geodesic embeddings and planar graphs
Recommended article: Embeddings of graphs in Euclidean spaces
Recommended article: Q4998963
Recommended article: Q4002103
Recommended article: Embeddings of graphs
Recommended article: Embedding graphs in Euclidean space
Recommended article: Geometric representations of graphs
Recommended article: Q4410018
description: scientific article; zbMATH DE number 4120189