On Sullivan＇s Conjecture on Cycles in 4-free and 5-free Digraphs

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...

Full description

Saved in:
Bibliographic Details
Published in:数学学报：英文版 2013 (1), p.53-64
Main Author: Hao LIANG Jun Ming XU
Format: Article
Language:English
Subjects:
不相邻顶点
周期
子集
有向图
猜想
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1439-8516
1439-7617