Graphs whose vertices of degree at least 2 lie in a triangle

Open Access

Issue		RAIRO-Oper. Res. Volume 58, Number 6, November-December 2024


Page(s)		5063 - 5077
DOI		https://doi.org/10.1051/ro/2024198
Published online		06 December 2024

F. Brandenburg, On optimal beyond-planar graphs. Comput. Geom. Topol. 2 (2023) 1–15. [Google Scholar]
A. Brandst¨adt, Efficient domination and efficient edge domination: a brief survey, in Algorithms and Discrete Applied Mathematics. Vol. 10743 of Lecture Notes in Comput. Sci. Springer, Cham (2018) 1–14. [Google Scholar]
A. Brandst¨adt and R. Mosca, Dominating induced matchings for P₇-free graphs in linear time. Algorithmica 68 (2014) 998–1018. [CrossRef] [MathSciNet] [Google Scholar]
A. Brandst¨adt and R. Mosca, Finding dominating induced matchings in P₈-free graphs in polynomial time. Algorithmica 77 (2017) 1283–1302. [CrossRef] [MathSciNet] [Google Scholar]
A. Brandst¨adt and R. Mosca, Dominating induced matchings in S_1,2,4-free graphs. Discrete Appl. Math. 278 (2020) 83–92. [CrossRef] [MathSciNet] [Google Scholar]
A. Brandst¨adt and R. Mosca, Finding dominating induced matchings in S_2,2,3-free graphs in polynomial time. Discrete Appl. Math. 283 (2020) 417–434. [CrossRef] [MathSciNet] [Google Scholar]
A. Brandst¨adt and R. Mosca, Finding dominating induced matchings in S_1,1,5-free graphs in polynomial time. Discrete Appl. Math. 284 (2020) 269–280. [CrossRef] [MathSciNet] [Google Scholar]
A. Brandst¨adt and R. Mosca, Finding dominating induced matchings in PP₉-free graphs in polynomial time. Discuss. Math. Graph Theory 42 (2022) 1139–1162. [Google Scholar]
A. Brandst¨adt and R. Nevries, Efficient dominating and edge dominating sets for graphs and hypergraphs, in Encyclopedia of Algorithms. Springer (2016) 618–621. DOI: 10.1007/978-1-4939-2864-4689. [Google Scholar]
A. Brandst¨adt, C. Hundt and R. Nevries, Efficient edge domination on hole-free graphs in polynomial time, in: LATIN 2010: Theoretical Informatics. Vol. 6034 of Lecture Notes in Comput. Sci. Springer, Berlin (2010) 650–661. [CrossRef] [Google Scholar]
A. Brandst¨adt, A. Leitert and D. Rautenbach, Efficient dominating and edge dominating sets for graphs and hypergraphs, in Algorithms and Computation – 23rd International Symposium, ISAAC 2012, Taipei, Taiwan, December 19–21, 2012. Proceedings, Vol. 7676 of Lecture Notes in Computer Science, edited by K. Chao, T. Hsu and D. Lee. Springer (2012) 267–277. [Google Scholar]
D.M. Cardoso, J.O. Cerdeira, C. Delorme and P.C. Silva, Efficient edge domination in regular graphs. Discrete Appl. Math. 156 (2008) 3060–3065. [CrossRef] [MathSciNet] [Google Scholar]
D.M. Cardoso, N. Korpelainen and V.V. Lozin, On the complexity of the dominating induced matching problem in hereditary classes of graphs. Discrete Appl. Math. 159 (2011) 521–531. [CrossRef] [MathSciNet] [Google Scholar]
G. Chartrand, T.W. Haynes, M.A. Henning and P. Zhang, Stratification and domination in graphs. Discret. Math. 272 (2003) 171–185. [CrossRef] [Google Scholar]
N. Chiba and T. Nishizeki, Arboricity and subgraph listing algorithms. SIAM J. Comput. 14 (1985) 210–223. [CrossRef] [MathSciNet] [Google Scholar]
V.L. do Forte, M.C. Lin, A. Lucena, N. Maculan, V.A. Moyano and J.L. Szwarcfiter, Modelling and solving the perfect edge domination problem. Optim. Lett. 14 (2020) 369–394. [CrossRef] [MathSciNet] [Google Scholar]
D.L. Grinstead, P.J. Slater, N.A. Sherwani and N.D. Holmes, Efficient edge domination problems in graphs. Inf. Process. Lett. 48 (1993) 221–228. [CrossRef] [Google Scholar]
A. Hertz, V. Lozin, B. Ries, V. Zamaraev and D. de Werra, Dominating induced matchings in graphs containing no long claw. J. Graph Theory 88 (2018) 18–39. [CrossRef] [MathSciNet] [Google Scholar]
N. Korpelainen, V.V. Lozin and C. Purcell, Dominating induced matchings in graphs without a skew star. J. Discrete Algorithms 26 (2014) 45–55. [CrossRef] [MathSciNet] [Google Scholar]
J. Kratochvíl, Regular codes in regular graphs are difficult. Discrete Math. 133 (1994) 191–205. [CrossRef] [MathSciNet] [Google Scholar]
P. Laroche, Planar 1-in-3 satisfiability is NP-complete. ASMICSWorkshop on Tilings, Deuxième Journées Polyominos et pavages, Ecole Normale Supérieure de Lyon (1992). [Google Scholar]
M.C. Lin, F.J. Soulignac and J.L. Szwarcfiter, Arboricity h-index and dynamic algorithms. Theor. Comput. Sci. 426 (2012) 75–90. [CrossRef] [Google Scholar]
M.C. Lin, M.J. Mizrahi and J.L. Szwarcfiter, Fast algorithms for some dominating induced matching problems. Inf. Process. Lett. 114 (2014) 524–528. [CrossRef] [Google Scholar]
M.C. Lin, M.J. Mizrahi and J.L. Szwarcfiter, Efficient and perfect domination on circular-arc graphs. Electron. Notes Discret. Math. 50 (2015) 307–312. [CrossRef] [Google Scholar]
M.C. Lin, M.J. Mizrahi and J.L. Szwarcfiter, Exact algorithms for minimum weighted dominating induced matching. Algorithmica 77 (2017) 642–660. [CrossRef] [MathSciNet] [Google Scholar]
M.C. Lin, V. Lozin, V.A. Moyano and J.L. Szwarcfiter, Perfect edge domination: hard and solvable cases. Ann. Oper. Res. 264 (2018) 287–305. [CrossRef] [MathSciNet] [Google Scholar]
C.L. Lu and C.Y. Tang, Solving the weighted efficient edge domination problem on bipartite permutation graphs. Discrete Appl. Math. 87 (1998) 203–211. [CrossRef] [MathSciNet] [Google Scholar]
C.L. Lu, M.-T. Ko and C.Y. Tang, Perfect edge domination and efficient edge domination in graphs. Discrete Appl. Math. 119 (2002) 227–250. [CrossRef] [MathSciNet] [Google Scholar]
L. Markenzon, C. Justel and N. Paciornik, Subclasses of k-trees: characterization and recognition. Discrete Appl. Math. 154 (2006) 818–825. [CrossRef] [MathSciNet] [Google Scholar]
C. Moore and J. Robson, Hard tiling problems with simple tiles. Discrete Comput. Geom. 26 (2001) 573–590. [CrossRef] [MathSciNet] [Google Scholar]
V. Moyano, Edge dominating set problems: algorithms, bounds and properties. Ph.D. Thesis, Universidad de Buenos Aires (2017). [Google Scholar]
W. Mulzer and G. Rote, Minimum-weight triangulation is NP-hard. J. ACM 55 (2008) 1–29. [CrossRef] [Google Scholar]
R. Nevries, Efficient domination and polarity. Ph.D. Thesis, University of Rostock (2014). [Google Scholar]
D.J. Rose, On simple characterizations of k-trees. Discrete Math. 7 (1974) 317–322. [CrossRef] [MathSciNet] [Google Scholar]
M. Xiao and H. Nagamochi, Exact algorithms for dominating induced matching based on graph partition. Discrete Appl. Math. 190, 191 (2015) 147–162. [CrossRef] [Google Scholar]

Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.

Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.

Initial download of the metrics may take a while.