Product nordhaus-gaddum-type results for the induced path number involving complements with respect to Kn or Kn,n

Abstract

The induced path number p(G) of a graph G is defined as the minimum number of subsets into which the vertex set of G can be partitioned so that each subset induces a path. A Nordhaus-Gaddum-type result is a (tight) lower or upper bound on the sum (or product) of a parameter of a graph and its complement. If G is a subgraph of H} then the graph H - E{G) is the complement of G relative to H. In this paper, we consider product Nordhaus-Gaddum-type results for the parameter ρ when the relative complement is taken with respect to the complete graph K_n or the complete bipartite graph K_n,n.