×

zbMATH — the first resource for mathematics

Feedback arc number and feedback vertex number of Cartesian product of directed cycles. (English) Zbl 1453.05088
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\).
MSC:
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C20 Directed graphs (digraphs), tournaments
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C76 Graph operations (line graphs, products, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Karp, R. M.; Miller, R. E.; Thatcher, J. W., Reducibility among combinatorial problems, Complexity of Computer Computations, 85-103 (1972), New York-London: Plenum Press, New York-London
[2] Lu, C.; Tang, C. Y., A linear-time algorithm for the weighted feedback vertex problem on interval graphs, Information Processing Letters, 61, 2, 107-111 (1997) · Zbl 1336.68140
[3] Daniel Liang, Y., On the feedback vetex set in permutation graphs, Information Processing Letters, 52, 3, 123-129 (1994) · Zbl 0822.68083
[4] Ueno, S.; Kajitani, Y.; Gotoh, S., On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three, Discrete Mathematics, 72, 1-3, 355-360 (1988) · Zbl 0678.05026
[5] Bau, S.; Beineke, L. W., The decycling number of graphs, Australasian Journal of Combinatorics, 25, 285-298 (2002) · Zbl 0994.05079
[6] Festa, P.; Pardalos, P. M.; Resende, M. G. C.; Du, D. -Z.; Pardalos, P. M., Feedback set problems, Handbook of Combinatorial Optimization, Supplement vol. A, 209-259 (2000), Kluwer Academic Publishers
[7] Bonamy, M.; Dabrowski, K. K.; Feghali, C.; Johnson, M.; Paulusma, D., Independent feedback vertex sets for graphs of bounded diameter, Information Processing Letters, 131, 26-32 (2018) · Zbl 1422.68104
[8] Kuo, C.-J.; Hsu, C.-C.; Lin, H.-R.; Lin, K.-K., An efficient algorithm for minimum feedback vertex sets in rotator graphs, Information Processing Letters, 109, 9, 450-453 (2009) · Zbl 1209.68378
[9] Lima, C. V. G. C.; Rautenbach, D.; Souza, U. S.; Szwarcfiter, J. L., Decycling with a matching, Information Processing Letters, 124, 26-29 (2017) · Zbl 1416.05229
[10] Chang, H.; Fu, H.-L.; Lien, M.-Y., The decycling number of outerplanar graphs, Journal of Combinatorial Optimization, 25, 4, 536-542 (2013) · Zbl 1273.90222
[11] Madelaine, F. R.; Stewart, I. A., Improved upper and lower bounds on the feedback vertex numbers of grids and butterflies, Discrete Mathematics, 308, 18, 4144-4164 (2008) · Zbl 1154.05055
[12] Gentner, M.; Rautenbach, D., Feedback vertex sets in cubic multigraphs, Discrete Mathematics, 338, 12, 2179-2185 (2015) · Zbl 1318.05039
[13] Long, S.; Ren, H., The decycling number and maximum genus of cubic graphs, Journal of Graph Theory, 88, 3, 375-384 (2018) · Zbl 1393.05166
[14] Jiang, W.; Liu, T.; Wang, C.; Xu, K., Feedback vertex sets on restricted bipartite graphs, Theoretical Computer Science, 507, 41-51 (2013) · Zbl 1302.05191
[15] Gao, L.; Xu, X.; Wang, J.; Zhu, D.; Yang, Y., The decycling number of generalized Petersen graphs, Discrete Applied Mathematics, 181, 297-300 (2015) · Zbl 1304.05082
[16] Punnim, N., Decycling regular graphs, The Australasian Journal of Combinatorics, 32, 147-162 (2005) · Zbl 1070.05030
[17] Ren, H.; Yang, C.; Zhao, T.-X., A new formula for the decycling number of regular graphs, Discrete Mathematics, 340, 12, 3020-3031 (2017) · Zbl 1370.05105
[18] Bau, S.; Beineke, L. W.; Du, G.; Liu, Z.; Vandell, R. C., Decycling cubes and grids, Utliltas Mathematica, 59, 129-137 (2001) · Zbl 0977.05070
[19] Silberschatz, A.; Galvin, P. B.; Gagne, G., Operating System Concepts (2003), New York: John Wiley and Sons Inc., New York
[20] Wang, C.-C.; Lloyd, E. L.; Soffa, M. L., Feedback vertex sets and cyclically reducible graphs, Journal of the ACM, 32, 2, 296-313 (1985) · Zbl 0633.68064
[21] Bar-Yehuda, R.; Geiger, D.; Naor, J. S.; Roth, R. M., Approximation algorithms for the feedback vertex set problem with applications to constraint satisfaction and bayesian inference, SIAM Journal on Computing, 27, 4, 942-959 (1998) · Zbl 0907.68110
[22] Peleg, D., Size bounds for dynamic monopolies, Discrete Applied Mathematics, 86, 2-3, 263-273 (1998) · Zbl 0910.90286
[23] Peleg, D., Local majorities voting, small coalitions and controlling monopolies in graphs: a review, Theoretical Computer Science, 282, 2, 231-257 (2002) · Zbl 0997.68088
[24] Kleinberg, J.; Kumar, A., Proc. 10th ACM-SIAM Symposium on Discrete Algorithms
[25] Beineke, L. W.; Vandell, R. C., Decycling graphs, Journal of Graph Theory, 25, 1, 59-77 (1997) · Zbl 0870.05033
[26] Pike, D. A.; Zou, Y., Decycling cartesian products of two cycles, SIAM Journal on Discrete Mathematics, 19, 3, 651-663 (2005) · Zbl 1096.05030
[27] Lien, M.-Y.; Kuo, J.; Fu, H.-L., On the deycling number of generalized Kautz digraphs, Information Processing Letters, 115, 2, 209-211 (2015) · Zbl 1304.05062
[28] Figueroa, A. P.; Hernández-Cruz, C.; Olsen, M., The minimum feedback arc set problem and the acyclic disconnection for graphs, Discrete Mathematics, 340, 7, 1514-1521 (2017) · Zbl 1361.05047
[29] Even, G.; Naor, J. S.; Schieber, B.; Sudan, M., Approximating minimum feedback sets and multicuts in directed graphs, Algorithmica, 20, 2, 151-174 (1998) · Zbl 0897.68078
[30] Goemans, M. X.; Williamson, D. P., Primal-dual approximation algorithms for feedback problems in planar graphs, Combinatorica, 18, 1, 37-59 (1998) · Zbl 0928.90094
[31] Cai, M.-C.; Deng, X.; Zang, W., An approximation algorithm for feedback vertex sets in tournaments, SIAM Journal on Computing, 30, 6, 1993-2007 (2001) · Zbl 0980.68053
[32] Gaspers, S.; Mnich, M., Feedback Vertex Sets in Tournaments, Journal of Graph Theory, 72, 1, 72-89 (2013) · Zbl 1259.05070
[33] Mnich, M.; Teutrine, E., Improved bounds for minimal feedback vertex sets in tournaments, Journal of Graph Theory, 88, 3, 482-506 (2018) · Zbl 1393.05136
[34] Xiao, M.; Guo, J., A quadratic vertex kernel for feedback arc set in bipartite tournaments, Algorithmica, 71, 1, 87-97 (2015) · Zbl 1307.05214
[35] Trotter, W. T.; Erdös, P., When the cartesian product of directed cycles is Hamiltonian, Journal of Graph Theory, 2, 2, 137-142 (1978) · Zbl 0406.05048
[36] Keating, K., Multiple Hamiltonian graphs and digraphs, Annals of Discrete Mathematics, 27, 81-88 (1985)
[37] Bogdanowicz, Z. R., On decomposition of the Cartesian product of directed cycles of equal lengths, Discrete Applied Mathematics, 229, 148-150 (2017) · Zbl 1367.05174
[38] Liu, J.; Zhang, X.; Chen, X.; Meng, J., On domination number of Cartesian products of directed cycles, Information Processing Letters, 110, 171-173 (2010) · Zbl 1259.05134
[39] Zhang, X.; Liu, J.; Chen, X.; Meng, J., Domination number of Cartesian products of directed cycles, Information Processing Letters, 111, 1, 36-39 (2010) · Zbl 1259.05134
[40] Mollard, M., On the domination of Cartesian product of directed cycles: results for certain equivalance classes of legnths, Discussiones Mathematicae Graph Theory, 33, 387-394 (2013) · Zbl 1293.05271
[41] Shao, Z.; Zhu, E.; Lang, F., On the domination number of cartesian product of two directed cycles, Journal of Applied Mathematics, 2013 (2013) · Zbl 1397.05135
[42] Zhuang, W.; Yang, W.; Guo, X., On total domination number of Cartesian product of directed cycles, Ars Combinatoria, 124, 41-48 (2016) · Zbl 1413.05304
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.