Universal arrow-free graphs
type: Item
instance of: scholarly article
title: Universal arrow-free graphs
zbMATH Open document ID: 0921.05052
DOI: 10.1007/BF00052907
author: Menachem Kojman
author: Martin Goldstern
published in: Acta Mathematica Hungarica
publication date: 1999-09-14T00:00:00Z
review text: Let a family \({\mathcal G}\) of graphs be given. Then a graph \(G^*\in {\mathcal G}\) is called ``universal'' for \({\mathcal G}\) if every \(G\in {\mathcal G}\) is isomorphic to a subgraph of \(G^*\). On the other hand, \(G\) is said to be \(F\)-free with respect to a given graph \(F\) if \(F\) is not isomorphic to a subgraph of \(G\). The weak complexity of \({\mathcal G}\) is defined to be the minimal cardinality of a set \(I\) of graphs in \({\mathcal G}\) with the property that every member in \({\mathcal G}\) is embedded as a subgraph in at least one of the members of \(I\). The weak complexity of a class is one iff it has a universal element. In case of a class of countable graphs the weak complexity is at most \(2^{\aleph_0}\). In this paper the authors get two results. At first an infinite set of finite special trees \(A_n\) is considered; these graphs with \(n+5\) vertices, also called arrows, are defined and described. Then by using complete graphs and paths, \(A_n\)-free graphs are introduced, and also a connected \(A_n\)-free graph \(G_{\varepsilon}\) is constructed. For these graphs the authors prove an interesting property about the vertex degrees (Claims 1.3, 1.5 and 1.6). By using these results together with a further property (Claim 1.8) the authors receive Theorem 1.9 saying that for no \(n\) there is a universal countable \(A_n\)-free graph. This means that the weak complexity of the class of countable \(A_n\)-free graphs equals \(2^{\aleph_0}\). In Section 2 it is shown in a similar manner that also the class of all countable graphs omitting all cycles of length at most \(\ell\) \((\ell\geq 4)\) has no universal element and the weak complexity of the class of all such countable graphs is \(2^{\aleph_0}\) (Theorem 2.5).
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C60
zbMATH DE Number: 1336321
zbMATH Keywords: countable graphs
zbMATH Keywords: trees
zbMATH Keywords: cycles
zbMATH Keywords: paths
zbMATH Keywords: arrow-free graphs
zbMATH Keywords: complexity
Wikidata QID: Q56504570
reviewed by: Heinz-Joachim Presia
MaRDI profile type: Publication
cites work: There is no universal countable pentagon‐free graph
cites work: Some universal graphs
cites work: Universal elements and the complexity of certain classes of infinite graphs
description: scientific article; zbMATH DE number 1336321