Nonexistence of universal graphs without some trees
type: Item
instance of: scholarly article
title: Nonexistence of universal graphs without some trees
zbMATH Open document ID: 0889.05038
DOI: 10.1007/BF01200905
published in: Combinatorica
publication date: 1998-05-06T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C60
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 1149465
zbMATH Keywords: graph
zbMATH Keywords: universal graph
author: Zoltán Füredi
author: Péter Komjáth
MaRDI profile type: Publication
cites work: Subgraphs of graphs. I
cites work: There is no universal countable pentagon‐free graph
cites work: Graphs omitting sums of complete graphs
cites work: Graphs omitting a finite set of cycles
cites work: On the existence of countable universal graphs
cites work: Universal arrow-free graphs
cites work: Some universal graphs
cites work: Universal graphs without large bipartite subgraphs
cites work: Universal elements and the complexity of certain classes of infinite graphs
cites work: The complexity of a class of infinite graphs
cites work: Universal graphs and universal functions
cites work: Edge disjoint placement of graphs
cites work: Q4376496
description: scientific article; zbMATH DE number 1149465