首页 | 官方网站   微博 | 高级检索  
     


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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司    京ICP备09084417号-23

京公网安备 11010802026262号