✦ LIBER ✦

Extremal Digraph Results for Topological Complete Subgraphs

✍ Scribed by C. Jagger

Publisher: Elsevier Science
Year: 1998
Tongue: English
Weight: 143 KB
Volume: 19
Category: Article
ISSN: 0195-6698
DOI: 10.1006/eujc.1998.0231

No coin nor oath required. For personal study only.

✦ Synopsis

We determine, to within a constant factor, the maximum size of a digraph that does not contain a topological complete digraph DK p of order p. Let t 1 ( p) be defined for positive p by

where D denotes a digraph. We show that 1 16 p 2 < t 1 ( p) ≤ 44 p 2 . We also obtain results for containing topological tournaments, and a Turán-type result for containing a topological transitive tournament and a transitive tournament.

📜 SIMILAR VOLUMES

An Extremal Result for Subgraphs with Fe

An Extremal Result for Subgraphs with Few Edges

✍ S. Brandt 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 427 KB

We prove that whenever the edge number of a graph of order \(n \geqslant 517\) ensures that it contains every complete graph and every forest with at most \(n\) vertices and at most \(m\) edges, then the graph contains every graph with at most \(n\) vertices and \(m\) edges if \(m<n\). The required