Nonexistence of universal graphs without some trees (Q1385982)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Nonexistence of universal graphs without some trees
scientific article

    Statements

    Nonexistence of universal graphs without some trees (English)
    0 references
    6 May 1998
    0 references
    If \({\mathcal H}\) is a class of graphs then \(X\in {\mathcal H}\) is universal if every \(Y\in {\mathcal H}\) embeds into \(X\). The main result of this paper states that for \(r\geq 3\), if \(T\) is a finite tree with two neighbouring vertices of degree \(r+1\), \(1\), respectively, and of degree \(\leq r\) for the other vertices, then there is no universal, countable, \(T\)-free graph. This theorem is proved by a sequence of lemmata which are interesting on their own, too. For instance, it is shown, that for \(r\geq 3\) there exist \(r\)-regular, \(r\)-connected graphs with arbitrarily large girth. Some statements are deduced from properties of random regular graphs.
    0 references
    graph
    0 references
    universal graph
    0 references
    0 references
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references