Algorithmic Solution of Extremal Digraph Problems

From MaRDI portal





For a given family \({\mathcal L}\) of digraphs, the maximum number \(\text{ex}(n,{\mathcal L})\) of arcs a digraph on n vertices containing no member of \({\mathcal L}\) can possesses and the set \(\text{Ex}(n,{\mathcal L})\) of digraphs which attain this maximum are studied. In particular, the asymptotic behaviour of \(\text{ex}(n,{\mathcal L})/n^2\) is discussed in detail. For a square matrix \(A\), a sequence \(A(n)\) of digraphs, called matrix digraphs, are defined which are of, in some sense, simple structure. An algorithm is given to determine all matrices \(A\) such that each \(A(n)\) contains no member of \({\mathcal L}\), and has \(\text{ex}(n,{\mathcal L})+o(n^2)\) arcs as \(n\to \infty\).











This page was built for publication: Algorithmic Solution of Extremal Digraph Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3745867)