Propriedades estruturais de grafos matrogênicos

Abstract

Neste trabalho, estudamos os grafos matrogênicos. Apresentamos sua definição por meio de matroides, reunimos da literatura algumas de suas caracteri- zações e mostramos que são equivalentes. Além disso, estudamos um algoritmo de localização de autovalores e, como uma contribuição, demos o primeiro passo para localizar os autovalores de grafos matrogênicos em tempo linear. Mostramos que sua largura esperta em clique é menor ou igual a dois.

In this work, we study matrogenic graphs. We present their definition by matroids, gather from the literature some of their characterizations and show that they are equivalent. Also, we study an eigenvalue localization algortithm and, as a contribution, we took the first steps to locate the eigenvalues of matrogenic graphs in linear time. We show that their slick click width is less than or equal to two.