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 Creators ORCiD Kalyanasundaram, Subrahmanyam UNSPECIFIED
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:	Google Scholar

Actions (login required)

View Item

Statistics for this ePrint Item