Uma condição de suficiência para o problema da quase-bipartição em grafos de distância-hereditária

Speaker: Rodolfo Alves de Oliveira, INFES-UFF.

Date: 29 aug 2018, 13h.

Place: Room 407, Bloco H, Campus Gragoatá, UFF.

Abstract: Muitos dos problemas de partição do conjunto de vértices de um grafo apresentam aplicações interessantes, tais como no problema de agrupamento e detecção de relações em redes sociais, biológicas ou de transporte, no processamento de imagens, no desenvolvimento de sistemas VLSI, no {\it pagerank} de páginas web e nos problemas de escalonamento de tarefas.  Apresentaremos alguns aspectos teóricos sobre o problema de quase-bipartição na classe dos grafos de distância-hereditária. Considere um grafo $G =(V,E)$, uma quase-bipartição de $G$ é uma partição do conjunto de vértices $V$ em dois subconjuntos $\mathcal S$ e $\mathcal F$, onde $\mathcal S$ é um conjunto estável (ou independente) e $\mathcal F$ é um conjunto acíclico (isto é, induz um subgrafo acíclico). Veremos que o problema aplicado nos grafos de distância-hereditária possui um conjunto infinito de subgrafos proibidos dos quais não admitem uma quase-bipartição e mostraremos uma condição suficiente que garanta a existência da mesma para tal classe de grafos.m grafo G é dito hamiltoniano quando existe um ciclo que passa por todos os seus vértices. Um grafo é dito hiper-hamiltoniano quando a retirada de qualquer de seus vértices ainda produz um grafo hamiltoniano. Neste seminário, estudamos a noção de hiper-hamiltonicidade tanto do ponto de vista combinatório quando do ponto de vista da teoria espectral (isto é, da análise do espectro de matrizes associadas ao grafo). Nos dois contextos, fornecemos condições suficientes para a hiper-hamiltonicidade de um grafo.

Trabalho em conjunto conjunto com os professores Raquel Bravo (IC/UFF) e Uéverton Souza (IC/UFF), e o aluno Fábio Silva Jr. (IC/UFF).