PERTURBAÇÕES EM GRAFOS E SEUS EFEITOS SOBRE A CONECTIVIDADE ALGÉBRICA

Abstract

In this work, we consider the operation of a vertex removal and its effects to the algebraic connectivity of a graph, that is a spectral parameter denoted by a(G). That operation is applied to some families of graphs, such that complete split, pineapple, path-complete, double star, 1-sum and 2-sum graphs, and linking bridge between complete graphs. We used the function φ(v) = a(G) – a(G|v) to evaluate the algebraic connectivity variation when G|v is the graph obtained from G by removing the vertex v and all of its incident edges. A recent paper authored by Kirkland establishes necessary and sufficient conditions for G such that φ(v) = 1 and as a consequence of that result, he also shows that if G has a universal vertex v , then φ (v) = 1. From this fact, Kirkland has risen the question: "What can we say about φ(v) if vertex degree of v is (n - 2)?" Here, we partially solve this problem obtaning a necessary condition to a graph G such that φ(v) = 0 when v is of degree (n - 2). Also , we state two conjectures to φ(v) when v is of degree (n - 2).

Neste trabalho, determinamos as variações sofridas pela conectividade algébrica de um grafo, um parâmetro espectral, denotado por a(G), ao aplicarmos a operação de remoção de um vértice nos grafos das famílias split completo, abacaxi, caminho completo, dupla estrela e em grafos resultantes das operações 1-soma, 2-soma e ponte de ligação entre grafos completos. A função utilizada para medir esta variação é dada por φ(v) = a(G) – a(G|v), onde G|v é o grafo obtido de G pela remoção do vértice v e de todas as suas arestas incidentes. Um artigo recente de autoria de Kirkland estabeleceu condições necessárias e suficientes para G tal que φ(v) = 1 e, como consequência desse resultado, mostrou que, se G tem um vértice universal v e este vértice é removido, tem-se φ(v) = 1. A partir desse fato, o autor levantou a seguinte questão: "O que podemos dizer sobre φ(v) se o grau do vértice v é (n – 2)?” Nesse estudo, resolvemos parcialmente esta questão e obtivemos condições necessárias para um grafo G tal que φ(v) = 0 quando v tem grau (n – 2). Estabelecemos ainda duas conjecturas acerca da função φ(v) quando v tem grau (n – 2).