Pancyclicité dans la théorie des graphes hamiltonienne
Zengxian Tian · HAL (Le Centre pour la Communication Scientifique Directe) · 2021
Hamiltonian graph theory has been widely studied as one of the most important problems in graph theory. In this thesis, we work on generalizations of hamiltonian graph theory, and focus on the following topics: hamiltonian, pancyclicity, chorded pancyclic in the claw-free graphs, k-fan-connected graphs. For the pancyclicity problem, we show for k= 2, 3, if G= (V, E) is a k-connected graph of order n with V(G) =X₁⋃X₂⋃⋯⋃X_k, and for any pair of nonadjacent vertices x,y in Xᵢ with i= 1,2, ⋯,k, we have d(x) +d(y) ≥n, then G is pancyclic or G is a bipartite graph. For the hamiltonian problem of bipartite digraph, let D be a strongly connected balanced bipartite directed graph of order 2a≥10. Let x, y be distinct vertices in D, {x, y} dominates a vertex z if x→z and y→z; in this case, we call the pair {x, y} dominating. We show that D is hamiltonian for each dominating pair of vertices if their degree sum is at least 3a. In addition, we show some new sufficient conditions for bipancyclic and cyclability of digraphs. For the chorded pancyclic problem in claw-free graphs, we prove that every 2-connected claw-free graph G with |V(G)|≥35 is chorded pancyclic if the minimum degree is at least (n−2)/3. Furthermore, we show the number of chords in the chord cycle of length l(4≤l≤n). In addition, G is doubly chorded pancyclic. For the k-fan-connected problem, we prove that if for any three independent vertices x₁,x₂,x₃ in a graph G, d(x₁)+d(x₂)+d(x₃)−|N(x₁)⋂N(x₂)⋂N(x₃)|≥|V(G)|+k-1, then G is k-fan-connected and the lower bound is sharp. This main result deduces a 3-connected graph, under the same assumptions, is a Hamilton-connected. Finally, we would like to mention several new studies related to this thesis that is not included in the thesis. Moreover, we also cover other topics that I am interested in, such as hamiltonian line graphs, fault-tolerant hamiltonicity, graph coloring and so on. These topics are likely to become my further research fields.