Premium
Some probabilistic and extremal results on subdivisions and odd subdivisions of graphs
Author(s) -
Kjær Jørgensen Leif
Publication year - 1989
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190130111
Subject(s) - subdivision , combinatorics , mathematics , conjecture , probabilistic logic , graph , integer (computer science) , discrete mathematics , random graph , statistics , computer science , geography , archaeology , programming language
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.