On an adjacency property of almost all tournaments

DOI10.1016/J.DISC.2005.12.030MaRDI QIDQ2433700zbMATH OpenOpenAlexFDO

Authors Kathie Cameron, Anthony Bonato

Publication date 30 October 2006

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2005.12.030

zbMATH Keywords

\(n\)-existentially closed

Mathematics Subject Classification ID

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

Review text

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 \textit{P. Erdős} and \textit{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\).

Recommendations

• On 2-e.c. graphs, tournaments, and hypergraphs
• A Problem on Tournaments
• Bounds and constructions for n-e.c. tournaments
• On generalized exponents of tournaments
• scientific article; zbMATH DE number 3880740

Cites work

• A Constructive Solution to a Tournament Problem
• A prolific construction of strongly regular graphs with the n-e. c. property
• An Investigation of Colour-Critical Graphs with Complements of Low Connectivity
• Color-critical graphs on a fixed surface
• Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures
• Diametrically critical tournaments
• Graph theory
• scientific article; zbMATH DE number 3904630 (Why is no real title available?)
• scientific article; zbMATH DE number 3912417 (Why is no real title available?)
• scientific article; zbMATH DE number 3758364 (Why is no real title available?)
• scientific article; zbMATH DE number 554162 (Why is no real title available?)
• scientific article; zbMATH DE number 637278 (Why is no real title available?)
• scientific article; zbMATH DE number 3195967 (Why is no real title available?)
• On 2-e. c. line-critical graphs
• On a Problem in Graph Theory
• On a Problem of Schütte and Erdös
• On an adjacency property of almost all graphs
• On Subtournaments of a Tournament
• On the adjacency properties of paley graphs
• Some Common Properties for Regularizable Graphs, Edge-Critical Graphs and B-Graphs
• Some properties of non-bicolorable hypergraphs and the four-color problem
• The number of edges in critical strongly connected graphs
• The random graph
• Vertex critical 4-dichromatic circulant tournaments

Cited in

(8)

• Note on eccentricities in tournaments
• Oriented colourings of graphs with maximum degree three and four
• On 2-e.c. graphs, tournaments, and hypergraphs
• scientific article; zbMATH DE number 3880740 (Why is no real title available?)
• Subtournaments isomorphic to W₅ in a indecomposable tournament
• Bounds and constructions for n-e.c. tournaments
• 2- and 3-existentially closed tournaments
• The half-isomorphy and the finite strongly connected tournaments

This page was built for publication: On an adjacency property of almost all tournaments

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2433700)