ﻻ يوجد ملخص باللغة العربية
It is an intriguing question to see what kind of information on the structure of an oriented graph $D$ one can obtain if $D$ does not contain a fixed oriented graph $H$ as a subgraph. The related question in the unoriented case has been an active area of research, and is relatively well-understood in the theory of quasi-random graphs and extremal combinatorics. In this paper, we consider the simplest cases of such a general question for oriented graphs, and provide some results on the global behavior of the orientation of $D$. For the case that $H$ is an oriented four-cycle we prove: in every $H$-free oriented graph $D$, there is a pair $A,Bssq V(D)$ such that $e(A,B)ge e(D)^{2}/32|D|^{2}$ and $e(B,A)le e(A,B)/2$. We give a random construction which shows that this bound on $e(A,B)$ is best possible (up to the constant). In addition, we prove a similar result for the case $H$ is an oriented six-cycle, and a more precise result in the case $D$ is dense and $H$ is arbitrary. We also consider the related extremal question in which no condition is put on the oriented graph $D$, and provide an answer that is best possible up to a multiplicative constant. Finally, we raise a number of related questions and conjectures.
We show that a number of conditions on oriented graphs, all of which are satisfied with high probability by randomly oriented graphs, are equivalent. These equivalences are similar to those given by Chung, Graham and Wilson in the case of unoriented
We study Hamiltonicity in random subgraphs of the hypercube $mathcal{Q}^n$. Our first main theorem is an optimal hitting time result. Consider the random process which includes the edges of $mathcal{Q}^n$ according to a uniformly chosen random orderi
Kuhn, Osthus and Taraz showed that for each gamma>0 there exists C such that any n-vertex graph with minimum degree gamma n contains a planar subgraph with at least 2n-C edges. We find the optimum value of C for all gamma<1/2 and sufficiently large n.
We initiate the study of local topology of random graphs. The high level goal is to characterize local motifs in graphs. In this paper, we consider what we call the layer-$r$ subgraphs for an input graph $G = (V,E)$: Specifically, the layer-$r$ subgr
A theory of orientation on gain graphs (voltage graphs) is developed to generalize the notion of orientation on graphs and signed graphs. Using this orientation scheme, the line graph of a gain graph is studied. For a particular family of gain graphs