Índices de grafos livres de K s,t

Abstract

O problema de Turán, assim como seu derivado, o problema de Zarankiewicz, pertencem à área de teoria extremal de grafos, e são problemas em aberto. Na década de 90, houve o passo inicial ao que alguns autores chamam de teoria espectral extremal, que ocorre ao solucionar problemas extremais com o auxílio da teoria espectral de grafos. Motivados por tal expansão, apresentamos algumas cotas retiradas da literatura associadas ao problema de Zarankiewicz e às matrizes de adjacência, Laplaciana e Laplaciana sem sinal, juntamente com o passo a passo de suas demonstrações. Visamos fortalecer nosso “background” para uma futura interpretação do problema de Zarankiewicz associado à matriz Laplaciana normalizada, que se encontra em aberto. Por fim, apresentamos comentários e limitantes superiores ao número de arestas associadas aos resultados indicados acima. Indicamos, também, que trabalhos futuros pretendemos estudar.

The Turán problem, as well as its derivative, the Zarankiewicz problem, belong to the extremal graph theory and are open problems. In the 90’s started what some authors call the spectral extremal graph theory, which occurs by solving extremal problems with the aid of the spectral graph theory. Motivated by such expansion, we present some bounds, taken from the literature, associated with the Zarankiewicz problem and the adjacency, Laplacian, and signless Laplacian matrices, along with step-by-step demonstrations of each. Our aim is to strengthen our background for a future interpretation of the Zarankiewicz problem associated with the normalized Laplacian matrix, which also remains open. Finally, we comment on the results and present upper bounds for the number of edge associated with the results above. We also indicate what should be addressed by future studies.