One-to-one disjoint path covers in digraphs. (English) Zbl 1387.05192
Summary: A one-to-one \(k\)-disjoint directed path cover (\(k\)-DDPC for short) of a digraph \(D\) is a set of \(k\) disjoint directed paths joining source with sink that cover all the vertices of the digraph. Let \(\delta^0(D) : = \min \{\delta^+(D), \delta^-(D) \}\) be the minimum semi-degree of \(D\). We show that every digraph \(D\) of sufficiently large order \(n\) with \(\delta^0(D) \geqslant \lceil(n + k + 1) / 2 \rceil\) contains a one-to-one \(k\)-DDPC for any given one distinct source-sink. The undirected version and a Ore-type degree conditions of this result was proved earlier [C.-K. Lin et al., Discrete Math. 308, No. 7, 1330–1333 (2008; Zbl 1134.05045)].
MSC:
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
| 05C38 | Paths and cycles |
| 05C20 | Directed graphs (digraphs), tournaments |
| 05C07 | Vertex degrees |
| 05C35 | Extremal problems in graph theory |
Citations:
Zbl 1134.05045References:
| [1] | Lin, C. K.; Huang, H. M.; Tan, J. J.M.; Hsu, L. H., On spanning connected graphs, Discrete Math., 308, 7, 1330-1333 (2008) · Zbl 1134.05045 |
| [2] | Asdre, K.; Nikolopoulos, S. D., The 1-fixed-endpoint path cover problem is polynomial on interval graphs, Algorithmica, 58, 3, 679-710 (2010) · Zbl 1200.05212 |
| [3] | Ntafos, S. C.; Hakimi, S. L., On path cover problems in digraphs and applications to program testing, IEEE Trans. Softw. Eng., 5, 520-529 (1979) · Zbl 0412.68052 |
| [4] | Chen, X. B., Paired many-to-many disjoint path covers of the hypercubes, Inform. Sci., 236, 1, 218-223 (2013) · Zbl 1284.05274 |
| [5] | Dvořák, P. T., Partitions of faulty hypercubes into paths with prescribed endvertices, SIAM J. Discrete Math., 22, 4, 1448-1461 (2008) · Zbl 1187.05056 |
| [6] | Jo, S.; Park, J.-H.; Chwa, K.-Y., Paired many-to-many disjoint path covers in faulty hypercubes, Theoret. Comput. Sci., 513, 1-24 (2013) · Zbl 1352.68195 |
| [7] | Kim, S.-Y.; Lee, J.-H.; Park, J.-H., Disjoint path covers in recursive circulants \(G(2^m, 4)\) with faulty elements, Theoret. Comput. Sci., 412, 35, 4636-4649 (2011) · Zbl 1223.68083 |
| [8] | Kim, S. Y.; Park, J.-H., Paired many-to-many disjoint path covers in recursive circulants \(G(2^m, 4)\), IEEE Trans. Comput., 62, 12, 2468-2475 (2013) · Zbl 1372.68211 |
| [9] | Park, J.-H.; Kim, H.-C.; Lim, H.-S., Many-to-many disjoint path covers in hypercube-like interconnection networks with faulty elements, IEEE Trans. Parallel Distrib. Syst., 17, 3, 227-240 (2006) |
| [10] | Park, J.-H.; Kim, H.-C.; Lim, H.-S., Many-to-many disjoint path covers in the presence of faulty elements, IEEE Trans. Comput., 58, 4, 528-540 (2009) · Zbl 1368.68090 |
| [11] | Park, J.-H.; Ihm, I., Single-source three-disjoint path covers in cubes of connected graphs, Inform. Process. Lett., 113, 14, 527-532 (2013) · Zbl 1285.05106 |
| [12] | Park, J.-H.; Ihm, I., Disjoint path covers in cubes of connected graphs, Discrete Math., 325, 14-16, 65-73 (2014) · Zbl 1288.05145 |
| [13] | Shih, Y.-K.; Kao, S.-S., One-to-one disjoint path covers on \(k\)-ary \(n\)-cubes, Theoret. Comput. Sci., 412, 35, 4513-4530 (2011) · Zbl 1223.68086 |
| [14] | Zhang, S.; Wang, S., Many-to-many disjoint path covers in \(k\)-ary \(n\)-cubes, Theoret. Comput. Sci., 491 (2013) · Zbl 1277.68040 |
| [15] | Lim, H. S.; Kim, H. C.; Park, J. H., Ore-type degree conditions for disjoint path covers in simple graphs, Discrete Math., 339, 2, 770-779 (2016) · Zbl 1327.05276 |
| [16] | Dirac, G. A., Some theorems on abstract graphs, Proc. Lond. Math. Soc., 3, 1, 69-81 (1952) · Zbl 0047.17001 |
| [17] | Bondy, J. A.; Murty, U. S.R., Graph Theory with Applications, vol. 290 (1976), Citeseer · Zbl 1226.05083 |
| [18] | Overbeck-Larisch, M., Hamiltonian paths in oriented graph, J. Combin. Theory Ser. B, 21, 76-80 (1976) · Zbl 0294.05112 |
| [19] | Ferrara, M., Degree conditions for h-linked digraphs, Combin. Probab. Comput., 22, 5, 684-699 (2013) · Zbl 1282.05051 |
| [20] | Bondy, J.; Thomassen, C., A short proof of Meyniel’s theorem, Discrete Math., 19, 2, 195-197 (1977) · Zbl 0368.05029 |
| [21] | Kühn, D.; Osthus, D.; Young, A., \(k\)-ordered Hamilton cycles in digraphs, J. Combin. Theory, 98, 6, 1165-1180 (2008) · Zbl 1176.05042 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
