Paper Info
Title
A note on the number of edges guaranteeing a C4 in Eulerian bipartite digraphs
Abstract
Let G be an Eulerian bipartite digraph with vertex partition sizes in, n. We prove the following Turan-type result: If e(G) > 2mn/3 then G contains a directed cycle of length at most 4. The result is sharp. We also show that if e(G) = 2mn/3 and no directed cycle of length at most 4 exists, then G must be biregular. We apply this result in order to obtain an improved upper bound for the diameter of interchange graphs.
Year
Venue
Keywords
2002
ELECTRONIC JOURNAL OF COMBINATORICS
Discrete Mathematics and Combinatorics,Pure_mathematics/0111020
DocType
Volume
Issue
Journal
9.0
11
ISSN
Citations 
PageRank 
1077-8926
0
0.34
References 
Authors
1
2
Name
Order
Citations
PageRank
Jian Shen19214.67
Raphael Yuster21356153.53