Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 569.05023
Autor: Brown, William G.; Erdös, Paul; Simonovits, M.
Title: Inverse extremal digraph problems. (In English)
Source: Finite and infinite sets, 6th Hung. Combin. Colloq., Eger/Hung. 1981, Vol. I, Colloq. Math. Soc. János Bolyai 37, 119-156 (1984).
Review: [For the entire collection see Zbl 559.00001.]
Authors' abstract: "The authors continue their study of extremal problems of Turán type for directed graphs with multiple edges, now permitting any finite non-negative integer multiplicity. Having proved earlier (for the case of multiplicity at most 1) that there exists, for any family of "sample" digraphs, a matrix which represents the structure of an "asymptotically extremal sequence" of digraphs (containing none of the sample digraphs, and having a total number of arcs asymptotic to the maximum), they address themselves to the inverse problem: is every matrix so realized for some finite family of sample digraphs? They prove that this is indeed true for "dense" matrices - having certain integer entries, and such that an associated quadratic form attains its maximum for the standard simplex uniquely at an interior point."
Reviewer: G.Chaty
Classif.: * 05C20 Directed graphs (digraphs)
05C35 Extremal problems (graph theory)
05C50 Graphs and matrices
Keywords: extremal digraphs; Turán problem
Citations: Zbl 559.00001
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag