Algorithmic Solution of Extremal Digraph Problems
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\).
- Digraph extremal problems, hypergraph extremal problems, and the densities of graph structures
- Extremal problems for directed graphs
- scientific article; zbMATH DE number 3841900 (Why is no real title available?)
- scientific article; zbMATH DE number 3908459 (Why is no real title available?)
- scientific article; zbMATH DE number 3511563 (Why is no real title available?)
- scientific article; zbMATH DE number 863492 (Why is no real title available?)
- scientific article; zbMATH DE number 3224335 (Why is no real title available?)
- scientific article; zbMATH DE number 3285073 (Why is no real title available?)
- scientific article; zbMATH DE number 3298603 (Why is no real title available?)
- scientific article; zbMATH DE number 3333210 (Why is no real title available?)
- Maxima for Graphs and a New Proof of a Theorem of Turán
- On pancyclic digraphs
- On the theory of graphs
- On the jumping constant conjecture for multigraphs
- A Turán problem on digraphs avoiding distinct walks of a given length with the same endpoints
- Digraphs that contain at most \(t\) distinct walks of a given length with the same endpoints
- Turán number of 3-free strong digraphs with out-degree restriction
- Extremal digraphs avoiding distinct walks of length 3 with the same endpoints
- Extremal digraphs avoiding an orientation of \(C_4\)
- Turán-Ramsey theorems and simple asymptotically extremal structures
- Boundedness of optimal matrices in extremal multigraph and digraph problems
- Extremal problems for directed graphs
- Co-degree density of hypergraphs
- Turán problems for integer-weighted graphs
- Embedding Graphs into Larger Graphs: Results, Methods, and Problems
- scientific article; zbMATH DE number 3908459 (Why is no real title available?)
- Inequalities in probability theory and turán-type problems for graphs with colored vertices
- Turán-Ramsey Theorems and Kp-Independence Numbers
- On possible Turán densities
- scientific article; zbMATH DE number 7564191 (Why is no real title available?)
- Turán problems for mixed graphs
- The structure of hereditary properties and 2-coloured multigraphs
- Turán problems for oriented graphs
- Extremal oriented graphs avoiding 1-subdivision of an in-star
- Turán number of strong digraphs forbidden at least two triangles
- Extremal digraphs containing at most t paths of length 2 with the same endpoints
- Minimal hypergraph non-jumps
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)