Geometrical embeddings of graphs (Q1825202): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claims |
||
Property / author | |||
Property / author: Jan Reiterman / rank | |||
Property / author | |||
Property / author: Vojtěch Rödl / rank | |||
Property / author | |||
Property / author: Edita Šiňajová / rank | |||
Property / reviewed by | |||
Property / reviewed by: G. Wegner / rank | |||
Revision as of 03:07, 10 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Geometrical embeddings of graphs |
scientific article |
Statements
Geometrical embeddings of graphs (English)
0 references
1989
0 references
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.
0 references
threshold dimension
0 references
distance dimension
0 references
generalized threshold graphs
0 references
forbidden induced subgraphs
0 references
sphericity
0 references
spherical dimension
0 references
scalar product dimension
0 references
trees
0 references
complements of cycles
0 references