×

zbMATH — the first resource for mathematics

Sparse spanning \(k\)-connected subgraphs in tournaments. (English) Zbl 1371.05104

MSC:
05C20 Directed graphs (digraphs), tournaments
05C42 Density (toughness, etc.)
05C35 Extremal problems in graph theory
05C40 Connectivity
05C31 Graph polynomials
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] R.K. Ahuja, T.L. Magnanti, and J.B. Orlin, Network Flows: Theory, Algorithms, and Applications, Prentice-Hall, Upper Saddle River, NJ, 1993. · Zbl 1201.90001
[2] J. Bang-Jensen, Problems and conjectures concerning connectivity, paths, trees and cycles in tournament-like digraphs, Discrete Math., 309 (2009), pp. 5655–5667. · Zbl 1207.05067
[3] J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications, Springer, London, 2000. · Zbl 1170.05002
[4] J. Bang-Jensen, G. Gutin, and A. Yeo, A polynomial algorithm for the Hamiltonian cycle problem in semicomplete multipartite digraphs, J. Graph Theory, 29 (1998), pp. 111–132. · Zbl 0916.05049
[5] J. Bang-Jensen, J. Huang, and A. Yeo, Strongly connected spanning subdigraphs with the minimum number of arcs in quasi-transitive digraphs, SIAM J. Discrete Math., 16 (2003), pp. 335–343. · Zbl 1029.05063
[6] J. Bang-Jensen, J. Huang, and A. Yeo, Spanning \(k\)-arc-strong subdigraphs with few arcs in \(k\)-arc-strong tournaments, J. Graph Theory, 46 (2004), pp. 265–284. · Zbl 1057.05039
[7] P. Hajnal, Partition of graphs with condition on the connectivity and minimum degree, Combinatorica, 3 (1983), pp. 95–99. · Zbl 0529.05030
[8] J. Kim, D. Kühn, and D. Osthus, Bipartitions of highly connected tournaments, SIAM J. Discrete Math., 30 (2016), pp. 895–911. · Zbl 1336.05050
[9] D. Kühn, J. Lapinskas, D. Osthus, and V. Patel, Proof of a conjecture of Thomassen on Hamilton cycles in highly connected tournaments, Proc. London Math. Soc. (3), 109 (2014), pp. 733–762. · Zbl 1302.05069
[10] D. Kühn, D. Osthus, and T. Townsend, Proof of a tournament partition conjecture and an application to 1-factors with prescribed cycle lengths, Combinatorica, 36 (2015), pp. 451–469. · Zbl 1389.05058
[11] Y. Manoussakis, A linear-time algorithm for finding Hamiltonian cycles in tournaments, Discrete Appl. Math., 36 (1992), pp. 199–201. · Zbl 0776.05095
[12] A. Pokrovskiy, Highly linked tournaments, J. Combin. Theory Ser. B, 115 (2015), pp. 339–347. · Zbl 1319.05063
[13] A. Pokrovskiy, Edge disjoint Hamiltonian cycles in highly connected tournaments, Int. Math. Res. Not. IMRN, 2 (2017), pp. 429–467.
[14] C. Thomassen, Configurations in graphs of large minimum degree, connectivity, or chromatic number, in Combinatorial Mathematics: Proceedings of the Third International Conference (New York, 1985), Ann. New York Acad. Sci. 555, New York Academy of Sciences, New York, 1989, pp. 402–412.
[15] C. Thomassen, Graph decomposition with constraints on the connectivity and minimum degree, J. Graph Theory, 7 (1983), pp. 165–167. · Zbl 0515.05045
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.