On degree sum conditions for directed path-factors with a specified number of paths
On degree sum conditions for directed path-factors with a specified number of paths
复制标题
关于具有指定路径数的有向路径因子的度和条件
DOI：
10.1016/j.disc.2020.112114
复制
发表时间：
2020
影响因子：
0.8
通讯作者：
Pierre Montalbano
中科院分区：
文献类型：
--
作者：
Shuya Chiba;Eishi Mishio;Pierre Montalbano
有向图的有向路因子是由有向图中顶点不相交的有向路的并集构成的生成子有向图。本文给出了如下结果：若D是n≥（2 <$− 1）k− 1阶有向图，且对任意两个不同的顶点u和v，有dD+（u）+dD −（v）≥ n-k，且（u，v）<$A（D），则D有一个有向路因子，其中恰好有k条至少<$（≥ 2）阶的有向路.为了证明这一定理，我们讨论了有向图和具有完美匹配的二部图之间的对应关系，并考虑了有向图中长有向路存在的度条件。
A directed path-factor of a digraph is a spanning subdigraph consisting of a union of vertex-disjoint directed paths in the digraph. In this paper, we give the following result: If D is a digraph of order n≥(2 ℓ− 1) k− 1, and if d D+(u)+ d D−(v)≥ n− k for every two distinct vertices u and v with (u, v)∉ A (D), then D has a directed path-factor with exactly k directed paths of order at least ℓ (≥ 2). To show this theorem, we discuss the correspondence between digraphs and bipartite graphs with perfect matchings, and also consider degree conditions for the existence of long directed paths in digraphs.
有向图中的度数和周期
影响因子：
0.8
作者：
M. Heydemann
通讯作者：
M. Heydemann
关于二部图中包含 1 因子的 2 因子
DOI：
10.1016/s0012-365x(99)90061-4
发表时间：
1999
期刊：
Discret. Math.
影响因子：
--
作者：
Guantao Chen;R. Gould;M. Jacobson
通讯作者：
M. Jacobson
有向图中的最长路径
DOI：
10.1007/bf02579454
发表时间：
1981
期刊：
Comb.
影响因子：
--
作者：
J. Bermond;A. Germa;M. Heydemann;D. Sotteau
通讯作者：
D. Sotteau