The influence of the addition or deletion of a vertex or an edge on the induced path number of a graph

Abstract

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 B_i with ρ(B_i) = b _i for i = 1, 2,..., n where n ≥ 2 and k = ∑_i=1 ⁿ b_i - n + 1, then G is k- minus-critical if and only if each of the blocks B_i is a b_i-minus-critical graph.