Discrete Applied Mathematics Seminar by Minjung Michelle Kang: The Saturation Spectrum of Odd Cycles

Speaker: Minjung Michelle Kang, Ph.D. candidate, Illinois Institute of Technology

Title: The Saturation Spectrum of Odd Cycles

Abstract: Given a cycle \(_k\) on \(k\) vertices, we say that a graph \(G\) is \(C_k\)-saturated if it does not contain a \(C_k\)-subgraph, but the addition of any new edges to \(G\) creates at least one copy of \(C_k\). For \(k = 3\), this is a classical problem in extremal graph theory, i.e., how big/small can a triangle-free graph be? Mantel, in 1907, determined the maximum value, and later, the general construction was given by T{u}'ran. The questions for \(k = 3\) and \(k = 4\) are completely answered, and the next interesting question is for \(k \geq 5\). In this talk, we will characterize all pairs \((n,m)\) for which there is a \(C_5\)-saturated graph on \(n\) vertices and \(m\) edges and provide some general results about the size of \(C_k\)-saturated graphs when \(k\) is odd. This is joint work with R. Gould and A. Kundgen.

 

Discrete Applied Math Seminar

Request Zoom Link