Nordhaus-Gaddum results for the sum of the induced path number of a graph and its complement |
| |
Authors: | Johannes H Hattingh Ossama A Saleh Lucas C van Der Merwe Terry J Walters |
| |
Institution: | 1. Department of Mathematics, East Carolina University, Greenville, NC, 27858, USA 2. Department of Mathematics, University of Johannesburg, Auckland Park, 2006, South Africa 3. Department of Mathematics, University of Tennessee at Chattanooga, Chattanooga, TN, 37403, USA
|
| |
Abstract: | 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. |
| |
Keywords: | Nordhaus-Gaddum induced path number |
本文献已被 CNKI 维普 SpringerLink 等数据库收录! |
|