Destroying cycles in digraphs |
| |
Authors: | Molly Dunkum Peter Hamburger Attila P��r |
| |
Institution: | 1. Department of Mathematics and Computer Science, Western Kentucky University, Bowling Green, KY, 42101, USA
|
| |
Abstract: | For a simple directed graph G with no directed triangles, let β(G) be the size of the smallest subset X ∈ E(G) such that G\X has no directed cycles, and let γ(G) denote the number of unordered pairs of nonadjacent vertices in G. Chudnovsky, Seymour, and Sullivan showed that β(G) ≤ γ(G), and conjectured that β(G) ≤ $\tfrac{{\gamma (G)}}
{2}$\tfrac{{\gamma (G)}}
{2}
. In this paper we prove that β(G)<0.88γ(G). |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|