无向图可迹的一个充分条件

A Sufficient Condition on Traceable

无向图G是简单连通图,且最小度为δ.如果G中包含一条生成路,则G是可迹的.无向图G的叶子数L(G)是G中生成树所含的叶子数的最大数.基于L(G)和δ,证明了一个充分条件使得无向图G是可迹的,即设G为连通图,最小度为δ≤4.若δ≥(1/2)(L(G)+2),G是可迹的.

Let G be a simple connected graph with minimum degree δ.Then G is traceable if it contains a spanning path.The leaf number L(G) of G is defined as the maximum number of end vertices contained in a spanning tree of G.We prove a sufficient condition,depending on L(G) and δ,for G to be traceable.If δ≥(1/2)(L(G)+2),the graph G is traceable.