Quasi‐Random Oriented Graphs. Issue 2 (17th October 2012)

• Record Type: Journal Article
• Authors: Griffiths, Simon
• Is Part Of: Journal of graph theory. Volume 74:Issue 2(2013)
• Page Start: 198
• Page End: 209
• Publication Date: 2012-10-17
• Subjects: Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.21701
• Languages: English
• ISSNs: 0364-9024

Abstract

<abstract abstract-type="main"> <title>Abstract</title> <p>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 [5] in the case of unoriented graphs, and by Chung and Graham [3] in the case of tournaments. Indeed, our main theorem extends to the case of a general underlying graph <italic>G</italic>, the main result of [3] which corresponds to the case that <italic>G</italic> 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 <italic>D</italic> 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 <italic>H</italic>.</p> </abstract>