Some probabilistic and extremal results on subdivisions and odd subdivisions of graphs

A probabilistic result of Bollobás and Catlin concerning the largest integer p so that a subdivision of K p is contained in a random graph is generalized to a result concerning the largest integer p so that a subdivision of A p is contained in a random graph for some sequence A 1 , A 2 ,… of graphs such that A i +1 contains a subdivision of A i . 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 K p , p = 4, 5, with odd paths or cycles is determined.