Minimum feedback arc set of m-free digraphs

DOI10.1016/J.IPL.2013.01.019MaRDI QIDQ2377233zbMATH OpenOpenAlexFDO

Authors Hao Liang, Jun-Ming Xu

Publication date 28 June 2013

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1204.4516

zbMATH Keywords

acyclic digraphcombinatorial problemsdirected cyclefeedback arc set

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Paths and cycles (05C38)

Abstract: For a simple digraph $G$, let $$ be the size of the smallest subset $XsubseteqE(G)$ such that $G-X$ has no directed cycles, and let $gamma(G)$ be the number of unordered pairs of nonadjacent vertices in $G$. A digraph $G$ is called $m$-free if $G$ has no directed cycles of length at most $m$. This paper proves that $$ for any $m$-free digraph $G$, which generalized some known results.

Recommendations

• On Sullivan's conjecture on cycles in 4-free and 5-free digraphs
• Directed graphs without short cycles
• Large feedback arc sets, high minimum degree subgraphs, and long cycles in Eulerian digraphs
• 3-free strong digraphs with the maximum size
• On Seymour's second neighborhood conjecture of \(m\)-free digraphs

Cited in

(10)

• On Sullivan's conjecture on cycles in 4-free and 5-free digraphs
• 3-free strong digraphs with the maximum size
• On Seymour's second neighborhood conjecture of \(m\)-free digraphs
• Directed graphs without short cycles
• Finding a minimum feedback arc set in reducible flow graphs
• scientific article; zbMATH DE number 1762085 (Why is no real title available?)
• Large feedback arc sets, high minimum degree subgraphs, and long cycles in Eulerian digraphs
• On signed digraphs with all cycles negative
• Extremal results on feedback arc sets in digraphs
• 4-Free Strong Digraphs with the Maximum Size

This page was built for publication: Minimum feedback arc set of \(m\)-free digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2377233)