The influence of the addition or deletion of a vertex or an edge on the induced path number of a graph - Broere, Izak; Jonck, Elizabeth; Domke, Gayla S. (Utilitas Mathematica, 2006)
The induced path number p(G) of a graph G is defined as the minimum number of subsets into which the vertex set V(G) of G can be partitioned such that each subset induces a path. In this paper we look at the influence of the addition or deletion of a vertex or an edge on the path partition number. If G is a graph such that ρ(G) = k and ρ(G - v) = k - 1 for every v ∈ V(G), then we say that G is k-minus-critical. We prove that if G is a connected graph consisting of cyclic blocks Bi with ρ(Bi) = b i for i = 1, 2,..., n where n ≥ 2 and k = ∑i=1 n bi - n + 1, then G is k- minus-critical if and only if each of the blocks Bi is a bi-minus-critical graph.