✦ LIBER ✦

An extremal function for digraph subcontraction

✍ Scribed by Jagger, Chris

Publisher: John Wiley and Sons
Year: 1996
Tongue: English
Weight: 400 KB
Volume: 21
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199603)21:3<343::aid-jgt10>3.0.co;2-i

No coin nor oath required. For personal study only.

✦ Synopsis

We determine, to within a constant factor, the maximum size of a digraph which has no subcontraction to the complete digraph DK, of order p. Let d(p) be defined for positive integers p by d(p) = inf{c; e(D) 2 clDI implies D % DK,}, where D denotes a digraph, and + denotes contraction. We show that 0 . 5 3 p , / E < d(p) 5 2 5 0 2 p , / G holds if p is sufficiently large. Hence the function d(p) differs by only a constant factor from the corresponding function for undirected graphs.

📜 SIMILAR VOLUMES

Extremal Digraph Results for Topological

Extremal Digraph Results for Topological Complete Subgraphs

✍ C. Jagger 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 143 KB

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 topol

The Extremal Function for Complete Minor

The Extremal Function for Complete Minors

✍ Andrew Thomason 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 190 KB

Extremal functions for rooted minors

✍ Paul Wollan 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 208 KB

## Abstract The graph __G__ contains a graph __H__ as a __minor__ if there exist pairwise disjoint sets {__S__~__i__~ ⊆ __V__(__G__)|__i__ = 1,…,|__V__(__H__)|} such that for every __i__, __G__[__S__~__i__~] is a connected subgraph and for every edge __uv__ in __H__, there exists an edge of __G__ w

An extremal bandwidth problem for bipart

An extremal bandwidth problem for bipartite graphs

✍ Robert C. Brigham; Julie R. Carrington; Ronald D. Dutton; Joseph Fiedler; Richar 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 119 KB 👁 2 views

An extremal problem for subdivisions ofK

An extremal problem for subdivisions ofK?5

✍ Mader, W. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 248 KB 👁 1 views

It is proved that every graph G with G ≥ 2|G| -5, |G| ≥ 6, and girth at least 5, except the Petersen graph, contains a subdivision of K - 5 , the complete graph on five vertices minus one edge.

An extremal problem for H-linked graphs

✍ Alexandr Kostochka; Gexin Yu 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 167 KB 👁 1 views

## Abstract We introduce the notion of __H__‐linked graphs, where __H__ is a fixed multigraph with vertices __w__~1~,…,__w__~m~. A graph __G__ is __H__‐__linked__ if for every choice of vertices υ~1~,…, υ~m~ in __G__, there exists a subdivision of __H__ in __G__ such that υ~i~ is the branch vertex