Abstrait

Connexité d'un graphe à partir de sa séquence de degrés et sa pertinence avec la conjecture de reconstruction

Saptarshi Naskar, Krishnendu Basuli, Samar Sen Sarma

Une suite d'entiers non négatifs peut représenter les degrés d'un graphe G et pour le graphe H, il peut y avoir de nombreuses fonctions de mappage 1 à 1 ou 1 à plusieurs différentes par lesquelles G peut être mappé dans H. C'est-à-dire qu'il est possible de construire des graphes isomorphes ou réguliers ou connectés ou déconnectés. Trouver la connexité d'un graphe à partir d'une suite de degrés est analogue au problème de la conjecture de reconstruction. Notre intention dans cet article est de déduire la connexité du graphe uniquement à partir de la suite de degrés et sans avoir besoin d'aucune autre information. Il est évident qu'il n'y a pas de conclusion unique sur la connexité d'un graphe donné à partir de l'algorithme que nous projetons ici. Cependant, nous pouvons dire que la séquence représente un graphe connecté ou déconnecté.