Extremal problems for directed graphs

We consider directed graphs without loops and multiple edges, where the exclusion of multiple edges means that two vertices cannot be joined by two edges of the same orientation. Let \(L_1, \ldots ,L_q\) be given digraphs. What is the maximum number of edges a digraph can have if it does not contain any \(L_i\) as a subgraph and has given number of vertices? We shall prove the existence of a sequence of asymptotical extremal graphs having fairly simple structure. More exactly: There exists a matrix \(A=(a_{i,j})_{i,j \leq r}\) and a sequence \(\{S^n \}\) of graphs such that (i) the vertices of \(S^n\) can be divided into classes \(C_1, \ldots ,C_r\) so that, if \(i \neq j\), each vertex of \(C_i\) is joined to each vertex of \(C_j\) by an edge oriented from \(C_i\) to \(C_j\) if and only if \(a_{i,j}=2\); the vertices of \(C_i\) are independent if \(a_{i,i}=0\); and otherwise \(a_{i,i}=1\) and the digraph determined by \(C_i\) is a complete acyclic digraph; (ii) \(S^n\) contains no \(L_i\) but any graph having \([\epsilon n^2]\) more edges than \(S^n\) must contain at least one \(L_i\). (Here the word graph is an ``abbreviation for ``directed graph or digraph.)

Recommendations

Cites work

Cited in

(45)

This page was built for publication: Extremal problems for directed graphs

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