×

On spanned subgraphs of graphs. (English) Zbl 0405.05031

Beiträge zur Graphentheorie und deren Anwendungen, vorgetr. auf dem int. Kolloq., Oberhof (DDR) 1977, 80-96 (1977).
[For the entire collection see Zbl 0387.00005.]
In this paper, theorems of the following type are proved: Let \(C\) be a class of (finite) graphs satisfying certain asymptotic conditions saying that for \(G\in C\), both \(G\) and its complement \(\overline G\) are large. Then for all \(G\in C\) and all \(H\) in some specified class of graphs, \(H\) is isomorphic to an induced subgraph of \(G\) provided the order of \(G\) is large enough compared to the order of \(H\), where the order of a graph is the number of vertices. Examples of two such results are the following. Theorem 1. Let \(\delta> 0\) and \(C(\delta)\) be the class of graphs \(G\) satisfying \(\deg_Gx\geq(\delta+1/4)n\) and \(\deg_{\overline G}\geq(\delta+1/4)n\) for all \(x\in V(G)\), where \(n\) is the order of \(G\). Then there are functions \(n(\delta)\), \(c(\delta)\) such that for all \(G\in C(\delta)\) with \(|V(G)|> n(\delta)\) and for all \(H\in D\) with \(| V(H)|\leq c(\delta)\log n\), where \(D\) is the class of complete bipartite graphs and their complements, \(H\) is isomorphic to an induced subgraph of \(G\). Theorem 2. Let \(c\) be a real number, and let \(C\) be the class of graphs \(G\) such that neither \(G\) nor its complement contains a complete graph with at least \(c\log n\) vertices, where \(n\) is the order of \(G\). Then there is a function \(n(c,k)\) such that for all graphs \(G\in C\) with at least \(n(c,k)\) vertices and for all graphs \(H\) of order \(k\), \(H\) is isomorphic to an induced subgraph of \(G\).
Reviewer: L.Lesniak-Foster

MSC:

05C35 Extremal problems in graph theory

Citations:

Zbl 0387.00005