×

On an adjacency property of almost all tournaments. (English) Zbl 1108.05048

The authors say a tournament \(T\) is \(k\)-existentially closed (or \(k\)-e.c.) if for every ordered pair of disjoint subsets \(A\) and \(B\) of the nodes of \(T\) with \(|A\cup B|= k\), there exists at least one node \(q\) that beats all nodes of \(A\) and loses to all nodes of \(B\). It follows from results of P. Erdős and L. Moser [Can. Math. Bull. 7, 351–356 (1964; Zbl 0129.34701)] almost all (large) tournaments \(T\) are \(k\)-e.c. for any fixed integer \(k\). The authors of the present paper show that there exists a 2-e.c. tournament \(T\) with \(n\) nodes if and only if \(n= 7\) or \(n\geq 9\).

MSC:

05C20 Directed graphs (digraphs), tournaments
05C35 Extremal problems in graph theory

Citations:

Zbl 0129.34701
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aharoni, R.; Berger, E., The number of edges in critical strongly connected graphs, Discrete Math., 234, 119-123 (2001) · Zbl 0987.05058
[2] Ananchuen, W.; Caccetta, L., On the adjacency properties of Paley graphs, Networks, 23, 227-236 (1993) · Zbl 0777.05095
[3] Ananchuen, W.; Caccetta, L., On tournaments with a prescribed property, Ars Combin., 36, 89-96 (1993) · Zbl 0794.05032
[4] Berge, C., Graphs and Hypergraphs (1973), North-Holland: North-Holland Amsterdam · Zbl 0483.05029
[5] C. Berge, Some Common properties for regularizable graphs, edge-critical graphs and B-graphs, Theory and Practice of Combinatorics, North-Holland Mathematical Studies, vol. 60, North-Holland, Amsterdam, 1982, pp. 31-44.; C. Berge, Some Common properties for regularizable graphs, edge-critical graphs and B-graphs, Theory and Practice of Combinatorics, North-Holland Mathematical Studies, vol. 60, North-Holland, Amsterdam, 1982, pp. 31-44. · Zbl 0501.05056
[6] Berge, C., About vertex-critical nonbicolorable hypergraphs, Austral. J. Combin., 9, 211-219 (1994) · Zbl 0842.05069
[7] Berge, C., Some properties of non-bicolorable hypergraphs and the four-color problem, First International Colloquium on Graphs and Optimization (GOI), 1992 (Grimentz), Discrete Appl. Math., 65, 73-79 (1996)
[8] Bollobás, B., Random Graphs (1985), Academic Press: Academic Press London · Zbl 0567.05042
[9] Bonato, A.; Cameron, K., On an adjacency property of almost all graphs, Discrete Math., 231, 103-119 (2001) · Zbl 0973.05043
[10] Bonato, A.; Cameron, K., On 2-e.c. line-critical graphs, J. Combin. Math. Combin. Comput., 38, 111-121 (2001) · Zbl 0981.05088
[11] Bondy, J. A.; Murty, U. S.R., Graph Theory with Applications (1976), North-Holland: North-Holland New York · Zbl 1134.05001
[12] Caccetta, L.; Erdős, P.; Vijayan, K., A property of random graphs, Ars Combin., 19, 287-294 (1985) · Zbl 0572.05036
[13] Cameron, P. J., The random graph, (Graham, R. L.; Nešetřil, J., Algorithms and Combinatorics, vol. 14 (1997), Springer: Springer New York), 333-351 · Zbl 0864.05076
[14] P.J. Cameron, D. Stark, A prolific construction of strongly regular graphs with the \(n\); P.J. Cameron, D. Stark, A prolific construction of strongly regular graphs with the \(n\) · Zbl 1006.05065
[15] Erdős, P., On a problem in graph theory, Math. Gaz., 47, 220-223 (1963) · Zbl 0117.17402
[16] Gallai, T., Kritische Graphen I, Magyar Tud. Akad. Mat. Kutató Int. Közl., 8, 165-192 (1963) · Zbl 0121.18401
[17] Graham, R. L.; Spencer, J. H., A constructive solution to a tournament problem, Canad. Math. Bull., 14, 45-48 (1971) · Zbl 0209.55804
[18] Moon, J. W., On subtournaments of a tournament, Canad. Math. Bull., 9, 297-301 (1966) · Zbl 0141.41204
[19] Neumann-Lara, V., Vertex critical 4-dichromatic circulant tournaments, Discrete Math., 170, 289-291 (1997) · Zbl 0876.05039
[20] Plesník, J., Diametrically critical tournaments, Časopis Pěst. Mat., 100, 361-370 (1975) · Zbl 0315.05108
[21] Schmerl, J. H.; Trotter, W. T., Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures, Discrete Math., 113, 191-205 (1993) · Zbl 0776.06002
[22] Szekeres, E.; Szekeres, G., On a problem of Schütte and Erdős, Math. Gaz., 49, 290-293 (1965) · Zbl 0134.43502
[23] Thomassen, C., Color-critical graphs on a fixed surface, J. Combin. Theory Ser. B, 70, 67-100 (1997) · Zbl 0883.05051
[24] B. Toft, An investigation of colour-critical graphs with complements of low connectivity, Advances in Graph Theory (Cambridge Combinatorial Conference, Trinity Colloquium, Cambridge, 1977); Ann. Discrete Math. 3 (1978) 279-287.; B. Toft, An investigation of colour-critical graphs with complements of low connectivity, Advances in Graph Theory (Cambridge Combinatorial Conference, Trinity Colloquium, Cambridge, 1977); Ann. Discrete Math. 3 (1978) 279-287. · Zbl 0388.05013
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.