Ph.D
Group : Graphs, ALgorithms and Combinatorics

Pancyclicity in hamiltonian graph theory

Starts on 10/10/2017
Advisor : LI, Hao

Funding : Bourse pour étudiant étranger
Affiliation : Université Paris-Saclay
Laboratory : LRI - GALaC

Defended on 18/10/2021, committee :

Research activities :

Abstract :
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₂ ⋃ ⋯ ⋃ Xk , 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.

CAUSAL LEARNING FOR DIAGNOSTIC SUPPORT


CAUSAL UNCERTAINTY QUANTIFICATION UNDER PARTIAL KNOWLEDGE AND LOW DATA REGIMES


MICRO VISUALIZATIONS: DESIGN AND ANALYSIS OF VISUALIZATIONS FOR SMALL DISPLAY SPACES
The topic of this habilitation is the study of very small data visualizations, micro visualizations, in display contexts that can only dedicate minimal rendering space for data representations. For several years, together with my collaborators, I have been studying human perception, interaction, and analysis with micro visualizations in multiple contexts. In this document I bring together three of my research streams related to micro visualizations: data glyphs, where my joint research focused on studying the perception of small-multiple micro visualizations, word-scale visualizations, where my joint research focused on small visualizations embedded in text-documents, and small mobile data visualizations for smartwatches or fitness trackers. I consider these types of small visualizations together under the umbrella term ``micro visualizations.'' Micro visualizations are useful in multiple visualization contexts and I have been working towards a better understanding of the complexities involved in designing and using micro visualizations. Here, I define the term micro visualization, summarize my own and other past research and design guidelines and outline several design spaces for different types of micro visualizations based on some of the work I was involved in since my PhD.