A probabilistic result of Bollobas and Catlin concerning the largest integer p so that a subdivision of K, is contained in a random graph is generalized to a result concerning the largest integer p so that a subdivision of A, is contained in a random graph for some sequence Al, A*, . . . of graphs such that Ai+l contains a subdivision of A;. A similar result is proved for subdivisions with odd paths or cycles. The result is applied to disprove a conjecture of Chartrand, Geller, and Hedetniemi. The maximum number of edges in a graph without a subdivision of Kp, p = 4,5, with odd paths or cycles is determined.
SUBDIVISIONS OF GRAPHS IN RANDOM GRAPHS
For notation and terminology not defined here, see Bollobfis [2].
In this paper edges occur with probability i, i.e., all graphs on n labeled vertices have equal probability. For any graph H, HS denotes a subdivision of H.
For any graph G let o(G) denote the largest integer p so that G contains a subdivision of the complete graph K,. Let E > 0. Erdos and Fajtlowicz [7] proved that almost every graph G of order n satisfies a ( G ) < (2 + E)& Bollobas and Catlin [3] proved that for almost every graph of order n.