Feedback arc number and feedback vertex number of Cartesian product of directed cycles
Directed graphs (digraphs), tournaments (05C20) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph operations (line graphs, products, etc.) (05C76)
Summary: For a digraph \(D\), the feedback vertex number \(\tau \left(D\right)\), (resp. the feedback arc number \(\tau' \left(D\right))\) is the minimum number of vertices, (resp. arcs) whose removal leaves the resultant digraph free of directed cycles. In this note, we determine \(\tau \left(D\right)\) and \(\tau' \left(D\right)\) for the Cartesian product of directed cycles \(D = \overrightarrow{C_{n_1}} \square \overrightarrow{C_{n_2}} \square \cdots \overrightarrow{C_{n_k}} \). Actually, it is shown that \(\tau' \left(D\right) = n_1 n_2 \cdots n_k \sum_{i = 1}^k 1 / n_i\), and if \(n_k \geq \dots \geq n_1 \geq 3\) then \(\tau \left(D\right) = n_2 \ldots n_k\).
- A linear-time algorithm for the weighted feedback vertex problem on interval graphs
- A new formula for the decycling number of regular graphs
- A quadratic vertex kernel for feedback arc set in bipartite tournaments
- An approximation algorithm for feedback vertex sets in tournaments
- An efficient algorithm for minimum feedback vertex sets in rotator graphs
- Approximating minimum feedback sets and multicuts in directed graphs
- Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference
- Decycling Cartesian Products of Two Cycles
- Decycling cubes and grids
- Decycling graphs
- Decycling with a matching
- Domination number of Cartesian products of directed cycles
- Feedback vertex sets and cyclically reducible graphs
- Feedback vertex sets in cubic multigraphs
- Feedback vertex sets in tournaments
- Feedback vertex sets on restricted bipartite graphs
- scientific article; zbMATH DE number 2186982 (Why is no real title available?)
- scientific article; zbMATH DE number 3914349 (Why is no real title available?)
- scientific article; zbMATH DE number 1744105 (Why is no real title available?)
- Improved bounds for minimal feedback vertex sets in tournaments
- Improved upper and lower bounds on the feedback vertex numbers of grids and butterflies
- Independent feedback vertex sets for graphs of bounded diameter
- Local majorities, coalitions and monopolies in graphs: A review
- On decomposition of the Cartesian product of directed cycles into cycles of equal lengths
- On the decycling number of generalized Kautz digraphs
- On the domination number of Cartesian product of two directed cycles
- On the domination of Cartesian product of directed cycles: results for certain equivalence classes of lengths
- On the feedback vertex set problem in permutation graphs
- On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three
- On total domination number of Cartesian product of directed cycles.
- Primal-dual approximation algorithms for feedback problems in planar graphs
- Reducibility among combinatorial problems
- Size bounds for dynamic monopolies
- The decycling number and maximum genus of cubic graphs
- The decycling number of generalized Petersen graphs
- The decycling number of outerplanar graphs
- The minimum feedback arc set problem and the acyclic disconnection for graphs
- When the cartesian product of directed cycles is Hamiltonian
This page was built for publication: Feedback arc number and feedback vertex number of Cartesian product of directed cycles
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2296552)
