اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدOne way cuts in oriented graphs
197
0
0.0
(
0
)
تأليف
Simon Griffiths
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
This paper has been withdrawn by the author.
قيم البحث
اقرأ أيضاً
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
graphs, and by Chung and Graham in the case of tournaments. Indeed, our main theorem extends to the case of a general underlying graph G the main result of Chung and Graham which corresponds to the case that G is complete. One interesting aspect of these results is that exactly two of the four orientations of a four-cycle can be used for a quasi-randomness condition, i.e., if the number of appearances they make in D is close to the expected number in a random orientation of the same underlying graph, then the same is true for every small oriented graph H
In this paper, we extend the concept of kings and serfs in tournaments to that of weak kings and weak serfs in oriented graphs. We obtain various results on the existence of weak kings(weak serfs) in oriented graphs, and show the existence of n-orien
ted graphs containing exactly k weak kings(weak serfs). Also, we give the existence of n-oriented graphs containing exactly k weak kings and exactly s weak serfs such that b weak kings from k are also weak serfs.
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
with complex units, matrix properties are established. As with graphs and signed graphs, there is a relationship between the incidence matrix of a complex unit gain graph and the adjacency matrix of the line graph.
Let $D=(G,mathcal{O},w)$ be a weighted oriented graph whose edge ideal is $I(D)$. In this paper, we characterize the unmixed property of $I(D)$ for each one of the following cases: $G$ is an $SCQ$ graph; $G$ is a chordal graph; $G$ is a simplicial gr
aph; $G$ is a perfect graph; $G$ has no $4$- or $5$-cycles; $G$ is a graph without $3$- and $5$-cycles; and ${rm girth}(G)geqslant 5$.
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 are
a 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.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
