有向图中爪的一个重要性质

摘要：

若 u1，…，up 和x为有向图D的顶点，记数列（P1，P2，…，Pp）为满足[x→ u1，u2，…， up]的有向路，使得每个 ui都是不同的，b（Pi）＝ x ，e（Pi）＝ ui 且 Pi 除在点x 外内部顶点均不相交，则称[ x→ u1，u2，…，up ]为有向图 D中的一个爪。我们证明了以下结论：如果[ x→ v1，…，vp－1，y]和[y→ vp ，…，v2p －1]（p≥1），那么存在一组整数1≤ i1＜…＜ ip ≤2 p－1，使得[x→vi1，…，vip ]。

关键词：爪、有向路、数列

分类号：O157.5(代数、数论、组合理论)

资助基金：山西大学商务学院院科研基金项目LX2010034

在线出版日期：2015-08-12（万方平台首次上网日期，不代表论文的发表时间）

页数：共2页

页码：355-356