Universal arrow-free graphs (Q1297747)

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).