PERTURBAÇÕES EM GRAFOS E SEUS EFEITOS SOBRE A CONECTIVIDADE ALGÉBRICA
Carregando...
Data
Autores
Título da Revista
ISSN da Revista
Título de Volume
Editor
CENTRO FEDERAL DE EDUCAÇÃO TECNOLÓGICA CELSO SUCKOW DA FONSECA
Resumo
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).
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).