Domination number and feedback vertex number of complements of line graphs

References

• Allan, R. B, Laskar, R. (1978). On domination and independent domination numbers of a graph. Discrete Math. 23(2): 73–76.
   Web of Science ®Google Scholar
• An, X, Wu, B. (2007). Hamiltonicity of complements of middle graphs. Discrete Math. 307(9-10): 1178–1184.
   Web of Science ®Google Scholar
• Bau, S, Beineke, L. W. (2002). The decycling number of graphs. Australas. J. Comb. 25: 285–298.
   Google Scholar
• Beineke, L. W, Bagga, J. S. (2021). Line Graphs and Line Digraphs. Switzerland: Springer.
   Google Scholar
• Bonamy, M., Dabrowski, K. K., Feghali, C., Johnson, M, Paulusma, D. (2018). Independent feedback vertex sets for graphs of bounded diameter. Inform. Process. Lett. 131: 26–32.
   Web of Science ®Google Scholar
• Bondy, J. A, Murty, U. S. R. (2008). Graph Theory. GTM 244, London: Springer.
   Google Scholar
• Brandstädt, A. (1992). On improved time bounds for permutation graphs problem 18th International Workshop on Graph-Theoretic Concepts in Computer Science, WG92. In: Lecture Notes in Comput. Sci., vol. 657, Springer, Berlin, pp. 1–10.
   Google Scholar
• Beineke, L. W, Vandell, R. C. (1997). Decycling graphs. J. Graph Theory 25(1): 59–77.
   Web of Science ®Google Scholar
• Chang, H., Fu, H. L, Lien, M. Y. (2013). The decycling number of outerplanar graphs. J. Comb. Optim. 25(4): 536–542.
   Web of Science ®Google Scholar
• Chartrand, G., Hevia, H., Jarrett, E. B, Schultz, M. (1997). Subgraph distances in graphs defind by edge transfers. Discrete Math. 170(1–3): 63–79.
   Web of Science ®Google Scholar
• Chen, X., Liu, J., Xie, D, Meng, J. (2016). Edge connectivity and super edge-connectivity of jump graphs. Inform. Optim. Sci. 37(2): 233–246.
   Web of Science ®Google Scholar
• Erdös, P., Saks, M, Sós, V. T. (1986). Maximum induced trees in graphs. J. Combin. Theory Ser. B. 41(1): 61–79.
   Web of Science ®Google Scholar
• Garey, M. R, Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman.
   Google Scholar
• Gernert, D. (1989). Forbidden and unavoidable subgraphs. Ars Combin. 27: 165–176.
   Web of Science ®Google Scholar
• Hedetniemi, S. T, Laskar, R. (1986). Recent results and open problems in domination theory. In Applications of Discrete Mathematics (Clemson, SC, 1986). Philadelphia, PA: SIAM, pp. 205–218.
   Google Scholar
• Karp, R. M. (1972). Reducibility among combinatorial problems. In: Complexity of Computer Computations (Miller, R. E., Thatcher, J. W. ed.). New York: Plenum Press, pp. 85–103.
   Google Scholar
• Kuo, C. J., Hsu, C. C., Lin, H. R, Lin, K. K. (2009). An efficient algorithm for minimum feedback vertex sets in rotator graphs. Inform. Process. Lett. 109(9): 450–453.
   Web of Science ®Google Scholar
• Liu, X., An, X, Wu, B. (2009). On perf eu; ct matchings of complements of line graphs. Ars Combin. 90: 45–54.
   Web of Science ®Google Scholar
• Gao, L., Xu, X., Wang, J., Zhu, D, Yang, Y. (2015). The decycling number of generalized Petersen graphs. Discrete Appl. Math. 181: 297–300.
   Web of Science ®Google Scholar
• Lu, C. L, Tang, C. Y. (1997). A linear-time algorithm for the weighted feedback vertex problem on interval graphs. Inform. Process. Lett. 61(2): 107–111.
   Web of Science ®Google Scholar
• McCuaig, W, Shepherd, B. (1989). Domination in graphs with minimum degree two. J. Graph Theory 13(6): 749–762.
   Web of Science ®Google Scholar
• Minty, G. J. (1980). On maximal independent sets of vertices in claw-free graphs. J. Combin. Theory Ser. B. 28(3): 284–304.
   Web of Science ®Google Scholar
• Ore, O. (1962). Theory of Graphs. Amer. Math. Soc. Colloq. Publ., Vol. 38 (Amer. Math. Soc., Providence, RI).
   Google Scholar
• Poljak, S. (1974). A note on stable sets and coloring of graphs. Comment. Math. Univ. Carolin. 15: 307–309.
   Google Scholar
• Reed, B. (1996). Paths, stars, and number three. Combinator. Probab. Comp. 5(3): 277–295.
   Google Scholar
• Sbihi, N. (1980). Algorithmes de recherche d’un stable de cardinalite maximum dans nn graphe sans etoile. Discrete Math. 29(1): 53–76.
   Google Scholar
• Ueno, S., Kajitani, Y, Gotoh, S. (1988). On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three. Discrete Math. 38: 355–360.
   Google Scholar
• Wu, B., Liu, X, Guo, X. (2008). Super-connected and hyper-connected jump graphs. Int. J. Comput. Math. 85(12): 1765–1769.
   Web of Science ®Google Scholar
• Wu, B, Meng, J. (2004). Hamiltonian jump graphs. Discrete Math. 289(1–3): 95–106.
   Web of Science ®Google Scholar
• Yannakakis, M. (1981). Node-deletion problem on bipartite graphs. SIAM J. Comput. 10(2): 310–327.
   Web of Science ®Google Scholar