부산대학교 도서관

The induced path number ρ( 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. Broere et al. proved that if G is a graph of order n, then $$\sqrt n \leqslant \rho \left( G \right) + \rho \left( {\bar G} \right) \leqslant \left\lceil {\tfrac{{3n}} {2}} \right\rceil$$. In this paper, we characterize the graphs G for which $$\rho \left( G \right) + \rho \left( {\bar G} \right) = \left\lceil {\tfrac{{3n}} {2}} \right\rceil$$, improve the lower bound on $$\rho \left( G \right) + \rho \left( {\bar G} \right)$$ by one when n is the square of an odd integer, and determine a best possible upper bound for $$\rho \left( G \right) + \rho \left( {\bar G} \right)$$ when neither G nor $$\bar G$$ has isolated vertices. [ABSTRACT FROM AUTHOR]