A Collection of Results on Saturation Number

Arun Jambulapati1, Ralph Faudree1
1The University of Memphis The University of Memphis

Abstract

A graph \( G \) is \( H \)-saturated if \( G \) does not contain \( H \) as a subgraph, but the addition of any edge between two nonadjacent vertices in \( G \) results in a copy of \( H \) in \( G \). The saturation number \( \operatorname{sat}(n, H) \) is the smallest possible number of edges in an \( n \)-vertex \( H \)-saturated graph. The values of saturation numbers for small graphs and \( H \) are obtained computationally, and some general results for specific path unions are also obtained.