首页 | 本学科首页   官方微博 | 高级检索  
     检索      


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

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