WorksMathematics
Distance- isolation of connected graphs
Abstract
If is a set of graphs and is a copy of a graph in , then we call an -graph. Let be a connected -vertex graph. For a subset of the vertex set , let denote the second closed neighbourhood of . Let denote the size of a smallest subset of such that intersects the -graphs contained by (equivalently, contains no -graph). For , let denote the set of connected graphs that have at least edges (and at least one vertex if ). By a well-known result of Meir and Moon, if . We show that if , and is not a -cycle. Hua and Liu recently showed that if is not a -vertex path or a -cycle or a -cycle, then there exists a subset of such that and each component of has a universal vertex. We strengthen this result by showing that if , and is not an -cycle or one of five -vertex graphs. It follows that if is not a -cycle or a -vertex graph or a -cycle. This also implies the result of Hua and Liu, and that if is the set of cycles, then unless is a -cycle or a -vertex graph containing a cycle. All these bounds are sharp.