𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On 4-cycles in random bipartite tournaments

✍ Scribed by Béla Bollobés; Ove Frank; Michał KarońSki

Publisher
John Wiley and Sons
Year
1983
Tongue
English
Weight
413 KB
Volume
7
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

We consider a random rn by n bipartite tournament T, , consisting of rnn independent random arcs which have a common probability p of being directed from the rn part to the n part. We determine the expected value and variance of the number of 4-cycles in T,,,, and the probability that T, , has no cycles. An asymptotic expression for this probability is also given when p = f and rn and n tend to infinity.

📜 SIMILAR VOLUMES

Hamiltonian cycles in bipartite quadrang
Hamiltonian cycles in bipartite quadrangulations on the torus
✍ Atsuhiro Nakamoto; Kenta Ozeki 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 133 KB 👁 2 views

## Abstract In this article, we shall prove that every bipartite quadrangulation __G__ on the torus admits a simple closed curve visiting each face and each vertex of __G__ exactly once but crossing no edge. As an application, we conclude that the radial graph of any bipartite quadrangulation on th

Proof of a conjecture on cycles in a bip
Proof of a conjecture on cycles in a bipartite graph
✍ Wang, Hong 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 244 KB 👁 2 views

It was conjectured in [Wang, to appear in The Australasian Journal of Combinatorics] that, for each integer k ≥ 2, there exists . This conjecture is also verified for k = 2, 3 in [Wang, to appear; Wang, manuscript]. In this article, we prove this conjecture to be true if n ≥ 3k, i.e., M (k) ≤ 3k. W

On the existence of specified cycles in
On the existence of specified cycles in a tournament
✍ Abdelhamid Benhocine; A. Pawel Wojda 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 241 KB 👁 1 views

For 2 s p s n and n 2 3, D(n, p) denotes the digraph with n vertices obtained from a directed cycle of length n by changing the orientation of p -1 consecutives edges. In this paper, we prove that every tournament of order n 2 7 contains D(n, p ) for p = 2, 3, ..., n. Furthermore, we determine the t

On the asymptotic distributions of subgr
On the asymptotic distributions of subgraph counts in a random tournament
✍ Pontus Andersson 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 191 KB 👁 2 views

A random tournament T is obtained by independently orienting the edges of n 1 the complete graph on n vertices, with probability for each direction. We study the 2 asymptotic distribution, as n tends to infinity, of a suitable normalization of the number of subgraphs of T that are isomorphic to a gi

On topological tournaments of order 4 in
On topological tournaments of order 4 in digraphs of outdegree 3
✍ Mader, W. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 371 KB 👁 1 views

It is proved that every finite digraph of minimum outdegree 3 contains a subdivision of the transitive tournament on 4 vertices.

On the number of cycles of length 4 in a
On the number of cycles of length 4 in a maximal planar graph
✍ Ahmad Fawzi Alameddine 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 148 KB 👁 2 views

## Abstract Let __p__ and __C__~4~ (__G__) be the number of vertices and the number of 4‐cycles of a maximal planar graph __G__, respectively. Hakimi and Schmeichel characterized those graphs __G__ for which __C__~4~ (__G__) = 1/2(__p__^2^ + 3__p__ ‐ 22). This characterization is correct if __p__ ≥