The insulation sequence of a graph Original Research Article

In a graph G, a k-insulated set S is a subset of the vertices of G such that every vertex in S is adjacent to at most k vertices in S, and every vertex outside S is adjacent to at least k+1 vertices in S. The insulation sequence i0,i1,i2,… of a graph G is defined by setting ik equal to the maximum cardinality of a k-insulated set in G. We determine the insulation sequence for paths, cycles, fans, and wheels. We also study the effect of graph operations, such as the disjoint union, the join, the cross product, and graph composition, upon k-insulated sets. Finally, we completely characterize all possible orderings of the insulation sequence, and prove that the insulation sequence is increasing in trees.