Unavoidable doubly connected large graphs

A connected graph is doubly connected if its complement is also connected. The following Ramsey-type theorem is proved in this paper. There exists a function h(n), defined on the set of integers exceeding three, such that every doubly connected graph on at least h(n) vertices must contain, as an induced subgraph, a doubly connected graph, which is either one of the following graphs or the complement of one of the following graphs: (1) P-n, a path on n vertices; (2) K-l.n(s), the graph obtained from K-l,K-n by subdividing an edge once; (3) K-2,K-n\e, the graph obtained from K-2,K-n by deleting an edge; (4) K-2,n(divided by), the graph obtained from K-2,K-n by adding an edge between the two degree-n vertices x(1) and x(2), and a pendent edge at each x(i). Two applications of this result are also discussed in the paper. (C) 2003 Elsevier B.V. All rights reserved.