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
    0 references
    0 references
    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

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references