平方树中的Pk-因子-《集美大学学报（自然科学版）》

文章信息/Info

Author(s):: FENG Xing; LI Jialin; (School of Science,Jimei University,Xiamen 361021,China)

摘要:: 如果H是图G的一个生成子图,并且H的每个连通分支都是包含k个顶点的路,则称生成子图H是图G的一个Pk因子。图G的平方图G2的顶点集为V(G),且在G2中两顶点相邻当且仅当这两顶点在图G中距离小于等于2。文中主要研究了图的Pk因子问题，通过树的特殊结构刻画了一些图的参数之间的关系,得到了在树的平方图中存在Pk因子的一个必要条件。最后,构造了两类满足结论中不等式取等的无穷图类。

Abstract:: A spanning subgraph H of G is a Pk-factor if each component of H is a path of k vertices.The square of a graph G,denoted by G2,is the graph with vertex set V(G) such that two vertices are adjacent in G2 if and only if their distance in G is at most 2.In this paper,we investigate the Pk-factor problem in graphs.By the special structure of the tree,this paper characterizes the relationships between some graph parameters and obtains a necessary condition for the existence of the Pk-factors in squares of trees.Finally, this paper constructs two infinite families of graphs that satisfy the equality condition in the conclusion’s inequalities.