Sesión Matemática DiscretaArista-dominación eficiente hereditaria
Germán Nicolás Sabatini
Universidad Nacional del Sur, Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
Un conjunto dominante eficiente en un grafo es un conjunto independiente de vértices D tal que todo vértice del grafo pertenece a D o es adyacente a un único vértice en D. El problema de decidir si un grafo admite un conjunto dominante eficiente es NP-completo para grafos en general e incluso restringido a distintas clases de grafos, como por ejemplo los grafos de línea o los grafos cordales. No obstante, se conocen clases de grafos para las cuales el problema es polinomial, como los grafos split y los grafos de co-comparabilidad. Una caracterización estructural de la familia de los grafos tales que todo subgrafo inducido admite un conjunto dominante eficiente fue dada por Milanič [3].
Un conjunto dominante de aristas eficiente en un grafo es un matching F tal que toda arista del grafo pertenece a F o es incidente a una única arista de F. De manera análoga a la dominación eficiente por vértices, el problema de decidir si un grafo admite un conjunto dominante de aristas eficiente es NP-completo en general, e incluso restringido a distintas clases de grafos como los grafos de línea [2]. También se conocen clases de grafos para las cuales el problema es polinomial, como los grafos bipartitos estrella-convexos [4] y los libres de $P_{10}$ [1].
Presentaremos una caracterización por subgrafos inducidos prohibidos de la clase de los grafos tales que todo subgrafo inducido admite un conjunto dominante de aristas eficiente. Además, ofreceremos una caracterización estructural de dicha clase describiendo las posibles componentes conexas de los grafos que la conforman.
Trabajo en conjunto con: Martín Darío Safe (Universidad Nacional del Sur, Argentina).
Referencias
[1] Andreas Brandstädt and Raffaele Mosca, Finding dominating induced matchings in P10-free graphs in polynomial time, Theoret. Comput. Sci. 990 (2024), Paper No. 114404, 16.
[2] Dana L. Grinstead, Peter J. Slater, Naveed A. Sherwani, and Nancy D. Holmes, Efficient edge domination problems in graphs, Inform. Process. Lett. 48 (1993), no. 5, 221–228.
[3] Martin Milanič, Hereditary efficiently dominatable graphs, J. Graph Theory 73 (2013), no. 4, 400–424.
[4] B.S. Panda and Juhi Chaudhary, Dominating induced matching in some subclasses of bipartite graphs, Theoretical Computer Science 885 (2021), 104–115.