zbMATH — the first resource for mathematics

Spanning \(k\)-arc-strong subdigraphs with few arcs in \(k\)-arc-strong tournaments. (English) Zbl 1057.05039
It is shown that every \(k\)-arc-strong tournament \(T\) contains a spanning \(k\)-arc-strong subdigraph with at most \(nk+136k^2\) arcs. Moreover, this is best possible in terms of the exponent on \(k\). Such a subdigraph can be found in polynomial time. The proof uses new results on digraphs in which the number of non-neighbors of each vertex is bounded by some constant \(c\). It is conjectured that for every \(k\)-arc-strong tournament \(T\) the minimum number of arcs in a \(k\)-arc-strong spanning subdigraph of \(T\) is equal to the minimum number of arcs in a spanning subdigraph of \(T\) with the property that every vertex has in- and outdegree at least \(k\).

05C20 Directed graphs (digraphs), tournaments
Full Text: DOI
[1] Aho, SIAM J Computing 1 pp 131– (1972)
[2] and Digraphs: Theory, Algorithms and Applications, Springer Verlag, London, 2001, 754 pp.+xxii. · Zbl 0958.05002
[3] Bang-Jensen, J Graph Theory 28 pp 171– (1998)
[4] Bang-Jensen, Siam J Disc Math 16 pp 335– (2003)
[5] Bang-Jensen, Combinatorica
[6] Bang-Jensen, J Algorithms 41 pp 1– (2001)
[7] Bessy, J Combin Theory 87 pp 289– (2003)
[8] Bondy, Discrete Mathematics 146 pp 289– (1995)
[9] Basic graph theory: Paths and circuits, Handbook of Combinatorics, Volume 1, and (Editors), Elsevier: Amsterdam, 1995, pp. 3-110.
[10] Camion, C R Acad Sci Paris 249 pp 2151– (1959)
[11] Chen, Discrete Math 44 pp 243– (1983)
[12] and Approximating minimum-size k-connected spanning subgraphs via matching (extended abstract), 37th IEEE Annual Symposium on Foundations of Computer Science (Burlington, VT, 1996), pp. 292-301.
[13] Edge-disjoint branchings, Combinatorial Algorithms (Editors), Academic Press: New York, 1973, pp. 91-96.
[14] Problem 15, (Editors), Theory of Graphs and its Applications, (1964), 161 p.
[15] Hsu, J Assoc Computing Machinery 22 pp 11– (1975) · Zbl 0316.05114 · doi:10.1145/321864.321866
[16] Khuller, SIAM J Computing 24 pp 859– (1995)
[17] Khuller, Disc Appl Math 69 pp 281– (1996)
[18] Lovász, J Combin Theory Ser B 21 pp 26– (1976)
[19] Finding a minimal transitive reduction in a strongly connected digraph within linear time, Graph Theoretic Concepts in Computer Science (Kerkrade, 1989), Springer Verlag, Berlin, 1990, pp. 244-259.
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.