Résumé - Une caractérisation constructive des graphes uniformément 4-connectés

Une caractérisation constructive des graphes uniformément 4-connectés

2025-07-10 11:30:36

{"Xiang Chen","Shuai Kou","Chengfu Qin","Liqiong Xu","Weihua Yang"}

{math.CO}

Le document présente une caractérisation constructive des graphes uniformément 4-connexes. Ces graphes sont caractérisés par le fait que le nombre maximum de chemins internes disjoint entre tout couple de sommets est exactement 4. Les auteurs fournissent une méthode pour construire de tels graphes en appliquant des opérations graphiques à des ensembles appropriés de sommets et d'arêtes. L'idée principale est que tout graphe uniformément 4-connexe peut être obtenu à partir de deux graphes de base, C2_5 ou C2_6, par une série d'opérations ∆_1 ou ∆_2. Ces opérations consistent en l'ajout de nouveaux sommets et d'arêtes tout en maintenant la 4-connexité uniforme. Le document commence par introduire certaines définitions et lemmes de base, tels que les concepts de chemins de chœur quasi 3-circuits, d'opérations ∆_1 et ∆_2, et de quasi 4-compatibilité. Il prouve ensuite plusieurs lemmes, tels que l'existence d'arêtes amovibles dans les graphes 4-connexes et la méthode de construction des graphes k-connexes. Le résultat principal du document est présenté dans le Théorème 9. Il stipule qu'un graphe G est uniformément 4-connexe si et seulement s'il est soit isomorphe à C2_5 ou C2_6, ou peut être construit en appliquant des opérations ∆_1 ou ∆_2 à un graphe uniformément 4-connexe plus petit. Pour prouver ce résultat, les auteurs montrent d'abord que tout graphe uniformément 4-connexe, à l'exception de C2_5 et C2_6, contient une arête amovible. Ils considèrent ensuite plusieurs cas en fonction du degré des extrémités de cette arête amovible. Dans chaque cas, ils montrent que G peut être construit en appliquant des opérations ∆_1 ou ∆_2 à un graphe uniformément 4-connexe plus petit. Le document conclut en illustrant comment résoudre le problème de construction d'une séquence de graphes 4-connexes satisfaisant certaines conditions, en utilisant les concepts et résultats présentés précédemment. En résumé, le document fournit une méthode constructive pour construire des graphes uniformément 4-connexes et les caractérise en utilisant des opérations graphiques et la quasi 4-compatibilité. Les résultats présentés dans le document peuvent être utiles pour étudier les propriétés des graphes uniformément connexes et leurs applications dans divers domaines.