Título: On Edge Domination of Graphs

Palestrante: Prof. Jayme Luiz Szwarcfiter (PESC) - Professor Emérito UFRJ e Pesquisador CNPq 1A.

Dia 17 de maio, quarta-feira, às 10 horas, Sala H-324B. 

Abstract:
Denote by G, an undirected simple graph, with vertex set V , and edge set E. An edge e ? E dominates itself and every edge adjacent to e. A set E? ? E is an (edge) dominating set of G, if each edge of E is dominated by some edge of E' . The domination is called efficient if each edge is dominated exactly once, and is called proper if each edge of E E? is dominated exactly once. In this talk, we survey and describe complexity results on these three types of edge domination. In particular, we consider the class of graphs, where each edge is contained in some triangle. We mention hardness and polynomial time cases on subclasses of this class, for edge domination problems.

Short Bio:
Jayme Luiz Szwarcfiter é Professor Emérito da UFRJ atuando no Programa de Engenharia de Sistemas e Computação da COPPE, no Instituto de Matemática e no Núcleo de Computação Eletrônica. Atualmente é Pesquisador Visitante do Instituto de Matemática e Estatística da UERJ. Atua nas áreas de Algoritmos, Teoria da Computação e Matemática Discreta. Publicou diversos livros-textos influentes nessas áreas, além da formação de dezenas de mestres e doutores. É Pesquisador 1-A do CNPq, Membro Titular da Academia Brasileira de Ciências, Grã-Cruz da Ordem Nacional do Mérito Científico, e recebeu inúmeros prêmios de destaque nacional e internacional por suas contribuições acadêmicas e científicas.