Propriedades estruturaus de grafos biclique

Abstract

Resumo: Esta tese apresenta o estudo sobre propriedades estruturais de grafos biclique em termos de tipos de intersecção entre bicliques maximais. Mostramos que grafos de bicliques mutuamente inclusas de bigrafos de inclusão de intervalos são grafos de permutação e que todo grafo de permutação é subgrafo induzido do grafo de bicliques mutuamente inclusas de algum bigrafo de intervalos. Também provamos a presença de certos subgrafos induzidos para intersecções apenas por vértices, mutuamente inclusas e por aresta não-mutuamente inclusa em grafos bipartidos. Introduzimos o grafo de inclusão de partes de bicliques e uma subclasse dos grafos de comparabilidade que é equivalente à classe dos grafos de inclusão de partes de bicliques de grafos livres de triângulos, do qual nós derivamos uma caracterização da classe dos grafos biclique de grafos livres de triângulos. Nós também sugerimos um algoritmo para a computação de uma pré-imagem do grafo de bicliques mutuamente inclusas de um grafo livre de triângulos. Introduzimos bicliques diferenciadas por aresta e por não-aresta — os quais chamamos de propriedades diferenciadoras—e provamos que toda inclusão mútua é um tipo de diferenciação por não-aresta, que todo par de bicliques intersectantes são diferenciadas por aresta ou por não-aresta e que cada tipo de propriedade diferenciadora é equivalente à presença de algum subgrafo induzido. Analisamos o grafo biclique do join entre dois grafos à luz das propriedades estruturais nós cobrimos neste trabalho e apresentamos alguns outros resultados de interesse sobre o estudo de grafos biclique.

Abstract: This thesis presents the study on structural properties of biclique graphs in terms of types of intersections between maximal bicliques. We show that the mutually included biclique graphs of interval containment bigraphs are permutation graphs and that every permutation graph is an induced subgraph of the mutually included biclique graph of some interval bigraph. We also prove the presence of certain induced subgraphs for vertex-only, mutually included and edge without mutual inclusion intersections in bipartite graphs. We introduce the inclusion graph of biclique parts of a graph and a subclass of comparability graphs that is equivalent to the class of inclusion graphs of biclique parts of triangle-free graphs, from which we derive a characterization of the class of biclique graphs of triangle-free graphs in terms of partially ordered sets. We also suggest an algorithm for the computation of a pre-image of the mutually included biclique graph of a triangle-free graph. We introduce the edge differentiated and non-edge differentiated bicliques—which we call the differentiated properties—and we prove the that every mutual inclusion is a type of differentiation by non-edge, that every pair of intersecting bicliques are differentiated by edge or non-edge, and that each type of differentiating property is equivalent to the presence of some induced subgraph. We analyze the biclique graph of a join between two graphs in light of the structutal properties we cover in this work and present some other results of interest on the study of biclique graphs.