Connected covering numbers. (English) Zbl 1331.05040
Summary: A connected covering is a design system in which the corresponding block graph is connected. The minimum size of such coverings are called connected coverings numbers. In this paper, we present various formulas and bounds for several parameter settings for these numbers. We also investigate results in connection with Turán systems. Finally, a new general upper bound, improving an earlier result, is given. The latter is used to improve upper bounds on a question concerning oriented matroid due to Las Vergnas.
MSC:
| 05B05 | Combinatorial aspects of block designs |
| 05B35 | Combinatorial aspects of matroids and geometric lattices |
| 05B40 | Combinatorial aspects of packing and covering |
| 51E05 | General block designs in finite geometry |
References:
| [1] | D.Applegate, E. M.Rains, and N. J. A.Sloane, On asymmetric coverings and covering numbers, J Combin Des11 (2003), 218-228. · Zbl 1013.05024 |
| [2] | A.Björner, M. LasVergnas, B.Sturmfels, N.White, and G. M.Ziegler, Oriented matroids, 2nd edn., Cambridge University Press, Cambridge, England, 1999. · Zbl 0944.52006 |
| [3] | D.Forge and J. L. RamírezAlfonsín, Connected coverings and an application to oriented matroids, Discrete Math187 (1998), 109-121. · Zbl 0958.05018 |
| [4] | D.Forge, J. L. RamírezAlfonsín, and H.Yeun, Disconnected coverings for oriented matroids via simultaneous mutations, Discrete Math258 (2002), 353-359. · Zbl 1019.52015 |
| [5] | M. K.FortJr. and G. A.Hedlund, Minimal coverings of pairs by triples, Pacific J Math8 (1958), 709-719. · Zbl 0084.01401 |
| [6] | D. M.Gordon, O.Patashnik, and G.Kuperberg, New constructions for covering designs, J Combin Des3 (1995), 269-284. · Zbl 0885.05053 |
| [7] | Y. O.Hamidoune and M. LasVergnas, Directed switching games on graphs and matroids, J Combin Theory Ser B40 (1986), 237-269. · Zbl 0589.90109 |
| [8] | L.Ji, An improvement on covering triples by quadruples, J Combin Des16 (2008), 231-243. · Zbl 1142.05010 |
| [9] | G.Katona, T.Nemetz, and M.Simonovits, On a problem of Turán in the theory of graphs, Mat Lapok15 (1964), 228-238. · Zbl 0138.19402 |
| [10] | K.Knauer, L. P.Montejano, and J. L. RamírezAlfonsín, How many circuits determine an oriented matroid?, http://arxiv.org/abs/1407.7388, 17 pages. |
| [11] | A. V.Kostochka, A class of constructions for Turán’s (3,4)‐problem, Combinatorica2 (1982), 187-192. · Zbl 0502.05046 |
| [12] | N. N.Kuzjurin, Explicit constructions of Rödl’s asymptotically good packings and coverings, Combin Probab Comput9 (2000), 265-276. · Zbl 0955.05024 |
| [13] | W.Mantel, Problem 28, Wiskundige Opgaven10 (1907), 320. |
| [14] | W. H.Mills, On the covering of triples by quadruples, Proceedings of the Fifth Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1974), Congr Numer X (1974), 563-581. · Zbl 0308.05009 |
| [15] | W. H.Mills, A covering of triples by quadruples, Proceedings of the Twelfth Southeastern Conference on Combinatorics, Graph Theory and Computing, Vol. II (Baton Rouge, La., 1981), Congr Numer33 (1981), 253-260. · Zbl 0487.05017 |
| [16] | V.Rödl, On a packing and covering problem, Eur J Combin6 (1985), 69-78. · Zbl 0565.05016 |
| [17] | J.Schönheim, On coverings, Pacific J Math14 (1964), 1405-1411. · Zbl 0128.24501 |
| [18] | A. F.Sidorenko, The method of quadratic forms in a combinatorial problem of Turán, Vestnik Moskov. Univ. Ser. I Mat Mekh76 (1982), 3-6. · Zbl 0495.05036 |
| [19] | A. F.Sidorenko, What we know and what we do not know about Turán numbers, Graphs Combin11 (1995), 179-199. · Zbl 0839.05050 |
| [20] | P.Turán, Eine Extremalaufgabe aus der Graphentheorie, Mat Fiz Lapok48 (1941), 436-452. · JFM 67.0732.03 |
| [21] | P.Turán, Research problems, Magyar Tud Akad Mat Kut Int Közl6 (1961), 417-423. |
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.
