Partite Saturation Problems

Abstract

Abstract We look at several saturation problems in complete balanced blow‐ups of graphs. We let denote the blow‐up of H onto parts of size n and refer to a copy of H in as partite if it has one vertex in each part of . We then ask how few edges a subgraph G of can have such that G has no partite copy of H but such that the addition of any new edge from creates a partite H . When H is a triangle this value was determined by Ferrara, Jacobson, Pfender, and Wenger in . Our main result is to calculate this value for when n is large. We also give exact results for paths and stars and show that for 2‐connected graphs the answer is linear in n whilst for graphs that are not 2‐connected the answer is quadratic in n . We also investigate a similar problem where G is permitted to contain partite copies of H but we require that the addition of any new edge from creates an extra partite copy of H . This problem turns out to be much simpler and we attain exact answers for all cliques and trees.

Locations

• Journal of Graph Theory - View
• arXiv (Cornell University) - View - PDF