On a minor-monotone graph invariant (Q1907104)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On a minor-monotone graph invariant |
scientific article |
Statements
On a minor-monotone graph invariant (English)
0 references
5 June 1996
0 references
Let \(G= (V, E)\) be a finite graph and \(d\in N\). A function \(\phi: V\to R^d\) is called a valid representation of \(G\) if for any halfspace \(H\) of \(R^d\) the set \(\phi^{- 1}(H)\) is nonempty and induces a connected subgraph of \(G\). Then \(\lambda(G)\) is defined as the largest \(d\) for which a valid representation \(\phi: V\to R^d\) exists. In other words, \(\lambda(G)\) is a sort of euclidean dimension of \(G\), somehow similar to the Colin de Verdière invariant \(\mu(G)\), which can be viewed as the spherical dimension of \(G\). If one denotes by \({\mathcal E}_d\) the class of finite graphs \(G\) with \(\lambda(G)\leq d\), then the following results hold: (1) \({\mathcal E}_d\) is minor closed; (2) \({\mathcal E}_d\) is closed under clique sums; (3) \({\mathcal E}_2\) consists of all series-parallel graphs; (4) \(K_5\) and \(V_8\) are the obstructions for \({\mathcal E}_3\).
0 references
minor-monotone graph invariant
0 references
forest
0 references
series-parallel graph
0 references
halfspace
0 references
valid representation
0 references
Colin de Verdière invariant
0 references
clique sums
0 references
series-parallel graphs
0 references