The induced path number p（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 hi. proved that if G is a graph o...The induced path number p（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 hi. proved that if G is a graph of order n, then 〈 p（G） ＋ p（G） 〈3n/2] . In this paper,_we characterize [3n/2], improve the lower bound on p（G） ＋ p（G） by one when the graphs G for which p（G） -4- p（G） = 3n n is the square of an odd integer, and determine a best possible upper bound for p（G） ＋ p（G） when neither G nor G has isolated vertices.展开更多
文摘The induced path number p（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 hi. proved that if G is a graph of order n, then 〈 p（G） ＋ p（G） 〈3n/2] . In this paper,_we characterize [3n/2], improve the lower bound on p（G） ＋ p（G） by one when the graphs G for which p（G） -4- p（G） = 3n n is the square of an odd integer, and determine a best possible upper bound for p（G） ＋ p（G） when neither G nor G has isolated vertices.
