×

zbMATH — the first resource for mathematics

Problems and conjectures concerning connectivity, paths, trees and cycles in tournament-like digraphs. (English) Zbl 1207.05067
Summary: We collect a substantial number of challenging open problems and conjectures on connectivity, paths, trees and cycles in tournaments and classes of digraphs which contain tournaments as a subclass. The list is by no means exhaustive but is meant to show that the area has a large number of interesting open problems. We also mention problems for general digraphs when they are relevant in the context.

MSC:
05C20 Directed graphs (digraphs), tournaments
05C40 Connectivity
05C38 Paths and cycles
05C05 Trees
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ailon, N.; Alon, N., Hardness of fully dense problems, Inform. and comput., 205, 8, 1117-1129, (2007) · Zbl 1121.68054
[2] Alion, N.; Charikar, M.; Newman, A., Aggregating inconsistent information: ranking and clustering, (), 684-693 · Zbl 1192.90252
[3] Alon, N., Ranking tournaments, SIAM J. discrete math., 20, 137-142, (2006) · Zbl 1112.05043
[4] Bampis, E.; Hell, P.; Manoussakis, Y.; Rosenfeld, M., Finding an antidirected Hamiltonian path starting with a forward arc from a given vertex in a tournament, Lect. notes comput. sci., 1120, 67-73, (1996)
[5] Bang-Jensen, J., Edge-disjoint in- and out-branchings in tournaments and related path problems, J. combin. theory ser. B, 51, 1, 1-23, (1991) · Zbl 0659.05052
[6] Bang-Jensen, J., Digraphs with the path-merging property, J. graph theory, 20, 2, 255-265, (1995) · Zbl 0832.05047
[7] Bang-Jensen, J.; Gutin, G., Generalizations of tournaments: A survey, J. graph theory, 28, 171-202, (1998) · Zbl 0920.05033
[8] Bang-Jensen, J.; Gutin, G., Digraphs: theory, algorithms and applications, (2001), Springer-Verlag London · Zbl 0958.05002
[9] Bang-Jensen, J.; Gutin, G.; Huang, J., Weakly Hamiltonian-connected ordinary multipartite tournaments, 14th british combinatorial conference (keele, 1993), Discrete math., 138, 1-3, 63-74, (1995) · Zbl 0834.05027
[10] Bang-Jensen, J.; Gutin, G.; Yeo, A., Hamiltonian cycles avoiding prescribed arcs in tournaments, Combin. probab. comput., 6, 3, 255-261, (1997) · Zbl 0878.05036
[11] Bang-Jensen, J.; Gutin, G.; Yeo, A., A polynomial algorithm for the Hamiltonian cycle problem in semicomplete multipartite digraphs, J. graph theory, 29, 111-132, (1998) · Zbl 0916.05049
[12] Bang-Jensen, J.; Huang, J.; Yeo, A., Strongly connected spanning subdigraphs with the minimum number of arcs in quasi-transitive digraphs, SIAM J. discrete math., 16, 335-343, (2003) · Zbl 1029.05063
[13] Bang-Jensen, J.; Huang, J.; Yeo, A., Spanning \(k\)-arc-strong subdigraphs with few arcs in \(k\)-arc-strong tournaments, J. graph theory, 46, 265-284, (2004) · Zbl 1057.05039
[14] Bang-Jensen, J.; Jordán, T., Adding and reversing arcs in semicomplete digraphs, Combin. probab. comput., 7, 1, 17-25, (1998) · Zbl 0892.05019
[15] Bang-Jensen, J.; Manoussakis, Y.; Thomassen, C., A polynomial algorithm for Hamiltonian-connectedness in semicomplete digraphs, J. algorithms, 13, 1, 114-127, (1992) · Zbl 0749.68057
[16] J. Bang-Jensen, M.H. Nielsen, Minimum cycle factors in quasi-transitive digraphs, Technical Report 7, Department of Mathematics and Computer Science, 2004 · Zbl 1134.90045
[17] Bang-Jensen, J.; Thomassen, C., A polynomial algorithm for the 2-path problem for semicomplete digraphs, SIAM J. discrete math., 5, 366-376, (1992) · Zbl 0759.05041
[18] Bang-Jensen, J.; Yeo, A., The minimum spanning strong subdigraph problem for extended semicomplete digraphs and semicomplete bipartite digraphs, J. algorithms, 41, 1-19, (2001) · Zbl 1002.68110
[19] Bang-Jensen, J.; Yeo, A., Decomposing \(k\)-arc-strong tournaments into strong spanning subdigraphs, Combinatorica, 24, 331-349, (2004) · Zbl 1064.05067
[20] Bang-Jensen, J.; Yeo, A., Making a tournament \(k\)-arc-strong by reversing or deorienting arcs, Discrete appl. math., 136, 161-171, (2004) · Zbl 1035.05045
[21] Bollobás, B.; Häggkvist, R., Powers of Hamilton cycles in tournaments, J. combin. theory ser. B, 50, 2, 309-318, (1990) · Zbl 0712.05030
[22] Charbit, P.; Thomassé, P.; Yeo, A., The minimum feedback arc set problem is NP-hard for tournaments, Combin. probab. comput., 16, 1, 1-4, (2007) · Zbl 1120.05038
[23] Chen, G.; Gould, R.; Li, H., Partitioning the vertices of a tournament into independent cycles, J. combin. theory, ser. B, 83, 213-220, (2001) · Zbl 1028.05038
[24] Cheriyan, J.; Thurimella, R., Approximating minimum-size \(k\)-connected spanning subgraphs via matching, SIAM J. comput., 30, 528-560, (2000) · Zbl 1049.90104
[25] Conitzer, V., Computing Slater rankings using similarities among candidates, ()
[26] Dalmazzo, M., Nombre d’arcs dans LES graphes \(k\)-arc-fortement connexes minimaux, C.R.acad. sci. Paris A, 285, 341-344, (1977) · Zbl 0367.05037
[27] Edmonds, J., Optimum branchings, J. res. natl. bur. stand. sect. B, 71B, 233-240, (1967) · Zbl 0155.51204
[28] Edmonds, J., Edge-disjoint branchings, (), 91-96
[29] El Sahili, A., Trees in tournaments, J. combin. theory, ser. B, 92, 183-187, (2004) · Zbl 1048.05040
[30] Fraisse, P.; Thomassen, C., Hamiltonian dicycles avoiding prescribed arcs in tournaments, Graphs combin., 3, 3, 239-250, (1987) · Zbl 0622.05028
[31] Frank, A., An algorithm for submodular functions on graphs, (), 97-120 · Zbl 0504.05059
[32] Frank, A., Connectivity and network flows, (), 111-177 · Zbl 0846.05055
[33] Frank, A.; Jordán, T., Minimal edge-coverings of pairs of sets, J. combin. theory ser. B, 65, 1, 73-110, (1995) · Zbl 0830.05051
[34] Frederickson, G.N.; Ja’Ja’, J., Approximation algorithms for several graph augmentation problems, SIAM J. comput., 10, 270-283, (1981) · Zbl 0461.05040
[35] Gould, R.; Guo, Y., Locally semicomplete digraphs with a factor composed of \(k\) cycles, J. Korean math. soc., 41, 895-912, (2004) · Zbl 1064.05070
[36] Guo, Y., Spanning local tournaments in locally semicomplete digraphs, 4th Twente workshop on graphs and combinatorial optimization (Enschede, 1995), Discrete appl. math., 79, 119-125, (1997) · Zbl 0884.05047
[37] Guo, Y.; Volkmann, L., On complementary cycles in locally semicomplete digraphs, Discrete math., 135, 1-3, 121-127, (1994) · Zbl 0816.05036
[38] Gupta, R.P., The chromatic index and the degree of a graph (abstract 66T-429), Notices amer. math. soc., (1966)
[39] G. Gutin, Cycles and paths in directed graphs, Ph.D. Thesis, School of Mathematics, Tel Aviv University, 1993
[40] Havet, F., Finding an oriented Hamiltonian path in a tournament, J. algorithms, 36, 253-275, (2000) · Zbl 0958.68193
[41] Havet, F.; Thomassé, S., Oriented Hamiltonian paths in tournaments: A proof of rosenfeld’s conjecture, J. combin. theory, ser B, 78, 243-273, (2000) · Zbl 1026.05053
[42] Hell, P.; Rosenfeld, M., Antidirected Hamiltonian paths between specified vertices of a tournament, Discrete appl. math., 117, 87-98, (2002) · Zbl 0996.05062
[43] Huang, J., A note on spanning local tournaments in locally semicomplete digraphs, Discrete appl. math., 89, 277-279, (1998) · Zbl 0919.05025
[44] Jordán, T., On the existence of \(k\) edge-disjoint 2-connected spanning subgraphs, J. combin. theory, ser. B, 95, 257-262, (2005) · Zbl 1075.05050
[45] Khuller, S.; Raghavachari, B.; Young, N., Approximating the minimum equivalent digraph, SIAM J. comput., 24, 4, 859-872, (1995) · Zbl 0830.68100
[46] Moon, J.W., Topics on tournaments, (1968), Holt, Rinehart and Winston New York · Zbl 0191.22701
[47] Nash-Williams, C.St.J.A., On orientations, connectivity and odd-vertex-pairings in finite graphs, Canad. J. math., 12, 555-567, (1960) · Zbl 0096.38002
[48] Raman, V.; Saurabh, S., Parameterized complexity of directed feedback arc set problems in tournaments, (), 484-492 · Zbl 1278.68110
[49] Reid, K.B., Two complementary circuits in two-connected tournaments, (), 321-334 · Zbl 0573.05031
[50] Song, Z.M., Complementary cycles of all lengths in tournaments, J. combin. theory ser. B, 57, 1, 18-25, (1993) · Zbl 0723.05062
[51] Thomassen, C., Hamiltonian-connected tournaments, J. combin. theory ser. B, 28, 2, 142-163, (1980) · Zbl 0435.05026
[52] Thomassen, C., Edge-disjoint Hamiltonian paths and cycles in tournaments, Proc. London math. soc. (3), 45, 1, 151-168, (1982) · Zbl 0486.05049
[53] Thomassen, C., Configurations in graphs of large minimum degree, connectivity, or chromatic number, Ann. New York acad. sci., 555, 402-412, (1989)
[54] Tuza, Z., Characterization of \((m, 1)\)-transitive and (3,2)-transitive semi-complete directed graphs, Discrete math., 135, 1-3, 335-347, (1994) · Zbl 0818.05050
[55] Vetta, A., Approximating the minimum strongly connected subgraph via a matching lower bound, (), 417-426 · Zbl 0987.05090
[56] Volkmann, L., Cycles in multipartite tournaments: results and problems, Discrete math., 245, 19-53, (2002) · Zbl 0996.05063
[57] Wormald, N.C., Subtrees of large tournaments, Lecture notes in math., 1036, 417-419, (1983) · Zbl 0521.05032
[58] Yeo, A., A polynomial time algorithm for finding a cycle covering a given set of vertices in a semicomplete multipartite digraph, J. algorithms, 33, 1, 124-139, (1999) · Zbl 0946.68105
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.