Geometrical embeddings of graphs (Q1825202): Difference between revisions

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.