Nordhaus-Gaddum Type Results for the Induced Path Number with Relative Complements in \(K_{m,n}\)

Johannes H.Hattingh1,2, Ossama A.Saleh3, Lucas C.Van der Merwe3, Terry J.Walters3
1Department of Mathematics, East Carolina University, Greenville, NC 27858 USA
2Department of Mathematics, University of Johannesburg, Auckland Park, 2006, SOUTH AFRICA
3Department of Mathematics, University of Tennessee at Chattanooga, Chattanooga, TN 37403 USA

Abstract

The induced path number \( \rho(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 Nordhaus-Gaddum type results for the parameter \( \rho \) when the relative complement is taken with respect to the complete bipartite graph \( K_{m,n} \).