Aplicações da Teoria Espectral em Algumas Classes de Grafos
Autores
|
1928 |
825,303,804
|
|
|
1929 |
825,303,804
|
|
|
1930 |
825,303,804
|
Informações:
Publicações do PESC
Os coeficientes do polinômio característicos de um grafo são determinados em função da contagem dos seus subgrafos elementares. São conhecidos os coeficientes dos seus quatro primeiros termos, que correspondem a aqueles de mais altos graus no polinômio. Neste trabalho, determinamos uma expressão algébrica para os quinto e sexto termos do polinômio característico de um grafo em função da determinação de subgrafos elementares especiais, que chamamos k-emparelhamentos. Introduzimos, aqui também, uma família nova de grafos, os cardigrafos, onde cada elemento é um grafo que possui cardinalidade de arestas dada em função do seu número de vértices. Esta família contem importantes classes de grafos, como os regulares, planares maximais, periplanares maximais(mops), árvores, k-árvores, etc...Estabelecemos propriedades para os cardigrafos que generalizam resultados conhecidos da literatura e determinamos aí uma subfamília, os grafos de densidade homogênea. Relacionamos estes grafos com os maxregulares e provamos que os seus índices tendem para o grau médio do grafo, à medida que o número de vértices aumenta.
The coefficients of the characteristic polynomial of a graph G are determined in terms of the counting of its elementary subgraphs. The four first terms of the coefficients of this polynomial, corresponding to its highest degrees, are already known. In this work, an algebraic expression to the fifths and sixths terms of the characteristic polynomial has been determined viewing the stabilishing of special elementary subgraphs which are called k-matching. This work also introduces a family ofnew graphs, the cardigraphs, where each element has its number ofvertices given in function of its number of edges. This family has important classes of graphs such as the trees, the regular graphs, the maximal outerplanar graphs (mops), the maximal planar graphs, etc. Properties that generalize well-known results of the literature have been established and a subfamily, graphs of homogeneous density, has been determined. These graphs have been associated with the maxregular graphs and it is proved that their indices tend to the medium degree ofthe graph, as its number ofvertices grows.