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 |
| |
Affiliation: | 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 leftlceil {tfrac{{3n}} {2}} rightrceil$ . In this paper, we characterize the graphs G for which $rho left( G right) + rho left( {bar G} right) = leftlceil {tfrac{{3n}} {2}} rightrceil$ , 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 等数据库收录! |
|