Existence de cycles dans les graphes bipartis et dans plusieurs familles de graphes généralisant la classe des graphes sans K₁,₃
Institution:
Paris 11Disciplines:
Directors:
Abstract EN:
In this thesis, we study sufficient conditions for the existence of cycles of given length in several families of graphs. The thesis consists of two parts: The first one is dedicated to bipartite graphs. We consider mainly bipartite balanced graphs that are hamiltonian, bipancyclic, S-cyclable and S-pancyclable. The conditions we investigate concern degree, independence number and k-biclosure. The second part concerns claw-free graphs. We examine several families that generalize the claw-free graphs family, mainly the λ-claw-free graphs and the S(K₁,₃)-free graphs. We look for sufficient conditions that insure some special cycles in those families of graphs or in their squares.
Abstract FR:
Dans cette thèse, nous apportons une contribution à l'étude de l'existence de cycles de longueur donnée dans certaines familles de graphes. La thèse se divise en deux parties. La première partie est dédiée aux graphes bipartis. Nous nous y intéressons aux graphes bipartis équilibrés hamiltoniens, bipancycliques, S-cyclables et S-pancyclables. Les conditions envisagées portent sur les degrés, le nombre d'indépendance biparti et la k-bifermeture. La seconde partie concerne les graphes sans K₁,₃ que nous appellerons aussi graphes "claw-free". On examine dans cette partie plusieurs familles de graphes qui généralisent la classe des graphes sans K₁,₃ , en particulier la famille des graphes λ-claw-free et celle des graphes sans S(K₁,₃), et l'on s'intéresse aux propriétés d'existence de cycles dans ces familles de graphes ou dans leurs carrés.