Largest digraphs contained in all n-tournaments
type: Item
instance of: scholarly article
title: Largest digraphs contained in all n-tournaments
zbMATH Open document ID: 0532.05032
DOI: 10.1007/BF02579345
author: Vera T. Sós
author: Nathan Linial
author: Michael Saks
published in: Combinatorica
publication date: 1983-01-01T00:00:00Z
review text: Let f(n) denote the largest integer such that there exists a directed graph D with n vertices and f(n) edges that is contained in every tournament with n vertices. The authors show, among other things, that \(c_ 1n\leq n \log_ 2n-f(n)\leq c_ 2n \log \log n\) for suitable constants \(c_ 1\) and \(c_ 2\).
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 3843781
zbMATH Keywords: subgraphs
zbMATH Keywords: tournament
reviewed by: J. W. Moon
MaRDI profile type: Publication
cites work: Realization of certain generalized paths in tournaments
cites work: Q5509547
cites work: Parity of paths and circuits in tournaments
cites work: Q5585195
cites work: Antidirected Hamiltonian circuits in tournaments
cites work: Q3680857
full work available at URL: https://doi.org/10.1007/bf02579345
OpenAlex ID: W1970492311
Recommended article: Tournaments and Semicomplete Digraphs
Recommended article: Q3838217
Recommended article: Maximum size of digraphs with some parameters
Recommended article: On tournaments and their largest transitive subtournaments
Recommended article: Asymptotic enumeration of tournaments with a given score sequence containing a specified digraph
Recommended article: Largest Induced Acyclic Tournament in Random Digraphs: A 2-Point Concentration
Recommended article: In-tournaments and semicomplete multipartite digraphs
Recommended article: Q5463549
Recommended article: Digraphs with maximum number of paths and cycles
description: scientific article; zbMATH DE number 3843781