4-cycles in mixing digraphs

Omid Amini; Simon Griffiths; Florian Huc

doi:10.1016/j.endm.2008.01.012

4-cycles in mixing digraphs

Omid Amini, Simon Griffiths, Florian Huc

Research output: Contribution to journal › Article › peer-review

Abstract

It is known that every simple graph with n^{3 / 2} edges contains a 4-cycle. A similar statement for digraphs is not possible since no condition on the number of arcs can guarantee an (oriented) 4-cycle. We find a condition which does guarantee the presence of a 4-cycle and our result is tight. Our condition, which we call f-mixing, can be seen as a quasirandomness condition on the orientation of the digraph. We also investigate the notion of mixing for regular and almost regular digraphs. In particular we determine how mixing a random orientation of a random graph is.

Original language	English
Pages (from-to)	63-68
Number of pages	6
Journal	Electronic Notes in Discrete Mathematics
Volume	30
Issue number	C
DOIs	https://doi.org/10.1016/j.endm.2008.01.012
Publication status	Published - 20 Feb 2008
Externally published	Yes

Keywords

digraphs
oriented 4-cycles
pseudo random digraphs

Access to Document

10.1016/j.endm.2008.01.012

Cite this

@article{0c1bb6f794294b0fbbe854ab59596d14,

title = "4-cycles in mixing digraphs",

abstract = "It is known that every simple graph with n3 / 2 edges contains a 4-cycle. A similar statement for digraphs is not possible since no condition on the number of arcs can guarantee an (oriented) 4-cycle. We find a condition which does guarantee the presence of a 4-cycle and our result is tight. Our condition, which we call f-mixing, can be seen as a quasirandomness condition on the orientation of the digraph. We also investigate the notion of mixing for regular and almost regular digraphs. In particular we determine how mixing a random orientation of a random graph is.",

keywords = "digraphs, oriented 4-cycles, pseudo random digraphs",

author = "Omid Amini and Simon Griffiths and Florian Huc",

year = "2008",

month = feb,

day = "20",

doi = "10.1016/j.endm.2008.01.012",

language = "English",

volume = "30",

pages = "63--68",

journal = "Electronic Notes in Discrete Mathematics",

issn = "1571-0653",

number = "C",

}

TY - JOUR

T1 - 4-cycles in mixing digraphs

AU - Amini, Omid

AU - Griffiths, Simon

AU - Huc, Florian

PY - 2008/2/20

Y1 - 2008/2/20

N2 - It is known that every simple graph with n3 / 2 edges contains a 4-cycle. A similar statement for digraphs is not possible since no condition on the number of arcs can guarantee an (oriented) 4-cycle. We find a condition which does guarantee the presence of a 4-cycle and our result is tight. Our condition, which we call f-mixing, can be seen as a quasirandomness condition on the orientation of the digraph. We also investigate the notion of mixing for regular and almost regular digraphs. In particular we determine how mixing a random orientation of a random graph is.

AB - It is known that every simple graph with n3 / 2 edges contains a 4-cycle. A similar statement for digraphs is not possible since no condition on the number of arcs can guarantee an (oriented) 4-cycle. We find a condition which does guarantee the presence of a 4-cycle and our result is tight. Our condition, which we call f-mixing, can be seen as a quasirandomness condition on the orientation of the digraph. We also investigate the notion of mixing for regular and almost regular digraphs. In particular we determine how mixing a random orientation of a random graph is.

KW - digraphs

KW - oriented 4-cycles

KW - pseudo random digraphs

U2 - 10.1016/j.endm.2008.01.012

DO - 10.1016/j.endm.2008.01.012

M3 - Article

AN - SCOPUS:39149098782

SN - 1571-0653

VL - 30

SP - 63

EP - 68

JO - Electronic Notes in Discrete Mathematics

JF - Electronic Notes in Discrete Mathematics

IS - C

ER -

4-cycles in mixing digraphs

Abstract

Keywords

Access to Document

Fingerprint

Cite this