Premium
An extremal function for digraph subcontraction
Author(s) -
Jagger Chris
Publication year - 1996
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(199603)21:3<343::aid-jgt10>3.0.co;2-i
Subject(s) - digraph , combinatorics , mathematics , constant (computer programming) , function (biology) , order (exchange) , undirected graph , directed graph , discrete mathematics , graph , computer science , evolutionary biology , biology , finance , economics , programming language
We determine, to within a constant factor, the maximum size of a digraph which has no subcontraction to the complete digraph DK p of order p. Let d ( p ) be defined for positive integers p by d ( p ) = inf{ c ; e ( D ) ≥ c | D | implies D (FANCY MORE THAN) DK p }, where D denotes a digraph, and (FANCY MORE THAN) denotes contraction. We show that 0.53 p √log 2 p < d ( p ) ≤ 2502 p √log 2 p holds if p is sufficiently large. Hence the function d ( p ) differs by only a constant factor from the corresponding function for undirected graphs. © 1996 John Wiley & Sons, Inc.