TITLE

On Sullivan's conjecture on cycles in 4-free and 5-free digraphs

AUTHOR(S)
Liang, Hao; Xu, Jun
PUB. DATE
January 2013
SOURCE
Acta Mathematica Sinica;Jan2013, Vol. 29 Issue 1, p53
SOURCE TYPE
Academic Journal
DOC. TYPE
Article
ABSTRACT
For a simple digraph G, let β( G) be the size of the smallest subset X ⊆ E( G) such that G−X has no directed cycles, and let γ( G) be the number of unordered pairs of nonadjacent vertices in G. A digraph G is called k-free if G has no directed cycles of length at most k. This paper proves that β( G) ≤ 0.3819 γ( G) if G is a 4-free digraph, and β( G) ≤ 0.2679 γ( G) if G is a 5-free digraph. These improve the results of Sullivan in 2008.
ACCESSION #
84088650

 

Related Articles

Share

Read the Article

Courtesy of NEW JERSEY STATE LIBRARY

Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics