Navegar

Colección

Datos Estadísticas

Artículo

Lin, M.C.; Moyano, V.A.; Rautenbach, D.; Szwarcfiter, J.L. "The maximum number of dominating induced matchings" (2015) Journal of Graph Theory. 78(4):258-268
Estamos trabajando para incorporar este artículo al repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

A matching M of a graph G is a dominating induced matching (DIM) of G if every edge of G is either in M or adjacent with exactly one edge in M. We prove sharp upper bounds on the number μ(G) of DIMs of a graph G and characterize all extremal graphs. Our results imply that if G is a graph of order n, then μ(G) & le; 3n/3 μ(G) & le; 4n/5 provided G is triangle-free; and μ(G) & le; 4 n-1/5 provided n ≤ 9 and G is connected. © 2014 Wiley Periodicals, Inc.

Registro:

Documento: Artículo
Título:The maximum number of dominating induced matchings
Autor:Lin, M.C.; Moyano, V.A.; Rautenbach, D.; Szwarcfiter, J.L.
Filiación:Conicet, and Instituto de Cálculo, Departamento de Computación, Universidad de Buenos Aires, Buenos Aires, Argentina
Instituto de Cálculo, Departamento de Computación, Universidad de Buenos Aires, Buenos Aires, Argentina
Institut für Optimierung und Operations Research, Universität ULM, Ulm, Germany
Instituto Nacional de Metrologia, Qualidade e Tecnologia, Instituto de Matemática and Coppe, Universidade Federal do Rio de Janeiro, Rio de Janeiro, Brazil
Palabras clave:Dominating induced matching; Fibonacci numbers; Number theory; Extremal graph; Fibonacci numbers; Graph G; Induced matchings; Triangle-free; Upper Bound; Graph theory
Año:2015
Volumen:78
Número:4
Página de inicio:258
Página de fin:268
DOI: http://dx.doi.org/10.1002/jgt.21804
Título revista:Journal of Graph Theory
Título revista abreviado:J. Graph Theory
ISSN:03649024
CODEN:JGTHD
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03649024_v78_n4_p258_Lin

Referencias:

  • Brandstödt, A., Hundt, C., Nevries, R., Efficient edge domination on holefree graphs in polynomial time (2010) Lect Notes Comput Sci, 6034, pp. 650-661
  • Brandstödt, A., Leitert, A., Rautenbach, D., Efficient dominating and edge dominating sets for graphs and hypergraphs (2012) Lect Notes Comput Sci, 7676, pp. 267-277
  • Brandstödt, A., Mosca, R., Dominating induced matching for P7-free graphs in linear time (2011) Lect Notes Comput Sci, 7074, pp. 100-109
  • Cardoso, D.M., Cerdeira, J.O., Delorme, C., Silva, P.C., Efficient edge domination in regular graphs (2008) Discrete Appl Math, 156, pp. 3060-3065
  • Cardoso, D.M., Korpelainen, N., Lozin, V.V., On the complexity of the dominating induced matching problem in hereditary classes of graphs (2011) Discrete Appl Math, 159, pp. 521-531
  • Cardoso, D.M., Lozin, V.V., Dominating induced matchings (2009) Lect Notes Comput Sci, 5420, pp. 77-86
  • Grinstead, D.L., Slater, P.J., Sherwani, N.A., Holmes, N.D., Efficient edge domination problems in graphs (1993) Inform Process Lett, 48, pp. 221-228
  • Korpelainen, N., A polynomial-time algorithm for the dominating induced matching problem in the class of convex graphs (2009) Electron Notes Discrete Math, 32, pp. 133-140
  • Lin, M.C., Mizrahi, M.J., Szwarcfiter, J.L., An O∗(1.1939n) time algorithm for minimum weighted dominating induced matching (2013) Lect Notes Comput Sci, 8283, pp. 558-567
  • Livingston, M., Stout, Q.F., Distributing resources in hypercube computers Proceedings of the 3rd Conference on Hypercube Concurrent Computers and Applications, ACM, 1988, pp. 222-231
  • Lu, C.L., Ko, M.-T., Tang, C.Y., Perfect edge domination and efficient edge domination in graphs (2002) Discrete Appl Math, 119, pp. 227-250
  • Lu, C.L., Tang, C.Y., Solving the weighted efficient edge domination problem on bipartite permutation graphs (1998) Discrete Appl Math, 87, pp. 203-211

Citas:

---------- APA ----------
Lin, M.C., Moyano, V.A., Rautenbach, D. & Szwarcfiter, J.L. (2015) . The maximum number of dominating induced matchings. Journal of Graph Theory, 78(4), 258-268.
http://dx.doi.org/10.1002/jgt.21804
---------- CHICAGO ----------
Lin, M.C., Moyano, V.A., Rautenbach, D., Szwarcfiter, J.L. "The maximum number of dominating induced matchings" . Journal of Graph Theory 78, no. 4 (2015) : 258-268.
http://dx.doi.org/10.1002/jgt.21804
---------- MLA ----------
Lin, M.C., Moyano, V.A., Rautenbach, D., Szwarcfiter, J.L. "The maximum number of dominating induced matchings" . Journal of Graph Theory, vol. 78, no. 4, 2015, pp. 258-268.
http://dx.doi.org/10.1002/jgt.21804
---------- VANCOUVER ----------
Lin, M.C., Moyano, V.A., Rautenbach, D., Szwarcfiter, J.L. The maximum number of dominating induced matchings. J. Graph Theory. 2015;78(4):258-268.
http://dx.doi.org/10.1002/jgt.21804