Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8900903 | Applied Mathematics and Computation | 2018 | 6 Pages |
Abstract
Let G=(V,E) be a graph of order n, and λ=(λ1,λ2,â¦,λp) a sequence of positive integers. The sequence λ is admissible for G if λ1+â¯+λp=n. Such an admissible sequence λ is said to be realizable in G if there exists a partition (V1,V2,â¦,Vp) of the vertex set V such that Vi induces a connected subgraph of order ni in G for each i. If every admissible sequence is realizable in G, then we say that G is arbitrarily partitionable (AP, for short). We show that if a tree T of maximum degree at most n+1 has a path containing all the vertices of degree n+1, then Tâ¡Cn has a Hamiltonian path. In particular, for any caterpillar T with maximum degree at most n+1,Tâ¡Cn is AP. In addition, if T is a caterpillar with Î(T)â¥n+4, then Tâ¡Cn is not AP. For the cases n+2â¤Î(T)â¤n+3, we present some sufficient conditions for a caterpillar T such that Tâ¡Cn is AP.
Related Topics
Physical Sciences and Engineering
Mathematics
Applied Mathematics
Authors
Fengxia Liu, Baoyindureng Wu, Jixiang Meng,