4-立方中匹配扩张成支撑2-路

Matchings extend to spanning 2-paths in 4-cube

图G的一个支撑子图称为G的一个支撑k-路,如果此支撑子图的分支是k条点不交的路。在运用归纳法构造超立方的哈密尔顿圈时,支撑k-路起着至关重要的作用。研究超立方的支撑k-路得到了以下结论:设u,v,x,y是Q_(4)中四个不同点满足p(u)=p(v)≠p(x)=p(y),M是Q_(4)-{u,v,x,y}的任意一个匹配,则Q_(4)中存在一个支撑2-路P_(u,x)+P_(v,y)经过匹配M。

A spanning subgraph of G whose components are k disjoint paths is a spanning k-path of G.When applying inductive methods to construct a Hamiltonian cycle in a hypercube,the spanning k-path palys a crucial role.In this paper,we obtainned the following result.Let u,v,x,y be pairwise distinct vertices in Q_(4)with p(u)=p(v)≠p(x)=p(y).If M was a matching in Q_(4)-{u,v,x,y},then there exists a spanning 2-path P_(u,x)+P_(v,y),y of Q_(4)passing through M.