Propriedades Estruturais e Espectrais do Produto Conormal de Certos Grafos

Vol 57, 2025 - 339603
Pôster
Favoritar este trabalho
Como citar esse trabalho?
Resumo

   O produto conormal de grafos, devido à sua lógica inclusiva destaca-se em diversas áreas
matemáticas e tecnológicas. Suas principais aplicações incluem o aprimoramento do reconhecimento
de padrões e processamento de linguagem natural. Tal operação
é formalmente definida por: o produto conormal G ⋆ H de um grafo G
de ordem m com conjunto de vértices V (G) = {v1, . . . , vm} e um grafo H de ordem n com
V (H) = {u1, . . . , un} define-se sobre o conjunto de vértices V (G) × V (H), onde a adjacência
entre vij = (vi, uj) e vrs = (vr, us) ocorre se vi ∼ vr em G ou uj ∼ us em H. A investigação foca
na presença de vértices gêmeos, definidos como vértices distintos u e v que compartilham a mesma
vizinhança aberta NG(u) = NG(v), denominados vértices gêmeos falsos, ou a mesma vizinhança
fechada NG[u] = NG[v], denominados vértices gêmeos verdadeiros.
A presença de gêmeos falsos em G ⋆ H garante a existência do autovalor λ = 0 na matriz
de adjacência. Analogamente, gêmeos verdadeiros implicam a ocorrência do autovalor λ = −1.
Demonstramos que vij e vrs são gêmeos falsos (ou verdadeiros) em G ⋆ H se, e somente se, os
seus componentes respectivos são gêmeos falsos (ou verdadeiros) nos grafos fatores G e H. Estruturalmente,
o diâmetro do produto conormal, denotado por diam(G ⋆H), desempenha um papel
crucial, sendo estabelecido que diam(G ⋆ H) = 2 sempre que nem G nem H possuem vértices
isolados ou se diam(H) ≤ 2. Essa característica permite analisar a matriz distância de um grafo W,
D(W) = [dij], cujas entradas representam a distância entre os vértices vi e vj em W. Observamos
que para grafos com diâmetro igual a 2, a matriz distância relaciona-se com a matriz de adjacência
A por meio da expressão D = 2(J − I) − A, em que I é a matriz identidade e J é a matriz cujas
as entradas são iguais a 1. Dentre os resultados que obtivemos, citamos:

Teorema 1. Se G⋆H é k-regular com n vértices e autovalores λ1 = k, λ2, . . . , λn, então o espectro
da matriz distância é {2n − 2 − k, −(2 + λ2), . . . ,−(2 + λn)}.
Corolário 1. Se G ⋆ H é completo com n vértices, então D(G ⋆ H) = J − I e seu espectro é
{n − 1,−1, . . . ,−1}.
   Os resultados obtidos evidenciam que a presença de vértices gêmeos desempenha papel
central na caracterização espectral do produto conormal, destacando a forte relação entre estrutura
e espectro em grafos.

Compartilhe suas ideias ou dúvidas com os autores!

Sabia que o maior estímulo no desenvolvimento científico e cultural é a curiosidade? Deixe seus questionamentos ou sugestões para o autor!

Faça login para interagir

Tem uma dúvida ou sugestão? Compartilhe seu feedback com os autores!

Instituições
  • 1 Universidade Federal Fluminense
  • 2 Departamento de Matemática / Instituto de Ciências Exatas / Universidade Federal Fluminense
  • 3 Universidade Federal Fluminense (UFF)
Eixo Temático
  • TAG – Teoria dos Grafos e Algoritmos Relacionados
Palavras-chave
Produto conormal
Vértices gêmeos
Matriz distância