Doctorat
Equipe : Graphes, Algorithmes et Combinatoire
Pancyclicité dans la théorie des graphes hamiltonienne
Début le 10/10/2017
Direction : LI, Hao
Ecole doctorale : ED STIC 580
Etablissement d'inscription : Université Paris-Saclay
Lieu de déroulement : LRI - GALaC
Soutenue le 18/10/2021 devant le jury composé de :
Directeur de thèse :
- M. Hao LI, Directeur de Recherche (HDR), Université Paris Saclay, France
Examinateurs :
- Mme Rongxia HAO, Professeure, Beijing Jiaotong University, Chine
- M. Antoine LOBSTEIN, Chargé de Recherche (HDR), Université Paris Saclay, France
Rapporteurs :
- M. Weihua YANG, Professeur, Taiyuan University of Technology, Chine
- M. Rong LUO, Professeur, West Virginia University, Etats-Unis
Activités de recherche :
Résumé :
La théorie hamiltonienne des graphes a été largement étudiée comme l’un des problèmes les plus importants de la théorie des graphes. Dans cette thèse, nous travaillons sur des généralisations de la théorie hamiltonienne des graphes, et nous nous concentrons sur les sujets suivants : hamiltonien, pan-cyclicité, pancyclicité à cordes dans les graphes sans griffes, graphes k-fan-connectés.
Pour le problème du pancyclicité, on montre pour k = 2, 3, si G = (V, E) est un graphe k-connecté d’ordre n avec V(G) = X₁ ⋃ X₂ ⋃ ⋯ ⋃ Xk , et pourtoute paire de sommets non adjacents x, y dans Xᵢ avec i = 1, 2, ⋯, k, on a d(x) + d(y) ≥ n, alors G est pancyclique ou G est un graphe bipartite.
Pour le problème hamiltonien du digraphe biparti, soit D un graphe orienté biparti équilibré fortement connecté d’ordre 2a ≥ 10. Soit x, y des sommets distincts dans D, {x, y} domine un sommet z si x → z et y → z; dans ce cas, nous appelons le couple {x, y} dominant. Nous montrons que D est hamiltonien pour chaque paire de sommets dominants si leur somme de degrés est d’au moins 3a. En outre, nous montrons quelques nouvelles conditions suffisantes pour la bipancyclique et la cyclabilité des digraphes.
Pour le problème pancyclique à cordes dans les graphes sans griffes, nous prouvons que tout graphe G sans griffes 2-connecté avec |V(G)| ≥ 35 est pancyclique à cordes si le degré minimum est d’au moins (n−2)/3. De plus, nous montrons le nombre de cordes dans le cycle à cordes de longueur l (4 ≤ l ≤ n). De plus, G est un pancyclique à double corde.
Pour le problème k-fan-connecté, nous prouvons que si pour trois sommets in dépendants x₁, x₂, x₃ dans un graphe G, d(x₁) + d(x₂) + d(x₃) − |N(x₁) ⋂ N(x₂) ⋂ N(x₃)| ≥ |V(G)| + k - 1, alors G est k-fan-connecté et la borne inférieure est tranchant. Ce résultat principal en déduit qu’un graphe 3-connexe, sous les mêmes hypothèses, est un Hamilton-connexe.
Enfin, nous aimerions mentionner plusieurs nouvelles études liées à cette thèse qui n’est pas incluses dans la thèse. De plus, nous couvrons également d’autres sujets qui m’intéressent, tels que les graphes de ligne hamiltoniens, l’hamiltonicité tolérante aux pannes, la coloration de graphe, etc. Ces sujets sont susceptibles de devenir mes autres domaines de recherche.
