A Note on Even Cycles and Quasi-Random Tournaments

Kalyanasundaram, Subrahmanyam and Shapira, A (2013) A Note on Even Cycles and Quasi-Random Tournaments. Journal of Graph Theory, 73. pp. 260-266. ISSN 0364-9024

Full text not available from this repository. (Request a copy)

Abstract

A cycle C={v1,v2,…,v1} in a tournament T is said to be even, if when walking along C, an even number of edges point in the wrong direction, that is, they are directed from vi+1 to vi. In this short article, we show that for every fixed even integer k≥4, if close to half of the k‐cycles in a tournament T are even, then T must be quasi-random. This resolves an open question raised in 1991 by Chung and Graham.

[error in script]
IITH Creators:
IITH CreatorsORCiD
Kalyanasundaram, SubrahmanyamUNSPECIFIED
Item Type: Article
Subjects: Computer science
Divisions: Department of Computer Science & Engineering
Depositing User: Library Staff
Date Deposited: 05 Sep 2019 05:16
Last Modified: 05 Sep 2019 06:18
URI: http://raiithold.iith.ac.in/id/eprint/6112
Publisher URL:
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 6112 Statistics for this ePrint Item