Nonexistence of universal graphs without some trees (Q1385982): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claims |
||
Property / author | |||
Property / author: Zoltan Fueredi / rank | |||
Property / author | |||
Property / author: Péter Komjáth / rank | |||
Revision as of 06:22, 10 February 2024
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