Abstrato

Conectividade de um grafo a partir da sua sequência de graus e é relevante para a conjetura de reconstrução

Saptarshi Naskar, Krishnendu Basuli, Samar Sen Sarma

Uma sequência de inteiros não negativos pode representar graus de um grafo G e para o grafo H. pode haver muitas funções de mapeamento diferentes de 1 para 1 ou 1 para muitos pelas quais G pode ser mapeado em H. Isto é viável para construir grafos isomórficos ou regulares ou ligados ou desligados. Encontrar a conectividade de um grafo a partir da sequência de graus é análogo ao problema da Conjetura de Reconstrução. É nossa intenção neste artigo inferir sobre a conexidade do grafo apenas a partir da sequência de graus e sem necessidade de qualquer outra informação. É evidente que não existe uma conclusão única sobre a conectividade de um determinado grafo a partir do algoritmo que aqui concebemos. No entanto, podemos dizer se a sequência representa um gráfico ligado ou desligado.