Français Anglais
Accueil Annuaire Plan du site
Home > Research results > Dissertations & habilitations
Research results
Ph.D de

Group : Graphs, ALgorithms and Combinatorics

Supereulerian graphs, hamiltonicity of graphs and several extremal problems in graphs

Starts on 24/01/2011
Advisor : LI, Hao

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

Defended on 27/09/2013, committee :
M. Ryjáček zdeněk, rapporteur, Proferssor of University of West Bohemia, Czech Republic

Mme. Guiying Yan, rapporteur, Proferssor of Chinese Academy of Sciences, China

M. Xiaofeng Guo, examinateur, Professor of, Xiamen University, China

M. Yannis MANOUSSAKIS, examinateur, Professor of Paris-sud University, FRANCE

Mme. Lianzhu Zhang, examinateur, Professor of Xiamen University, China

M. Hao Li, directeur de these, Directeur de Recherche of CNRS-LRI, FRANCE

Research activities :

Abstract :
In this thesis, we focus on the following topics: supereulerian graphs, hamiltonian line graphs, fault-tolerant hamiltonian laceability of Cayley graphs generated by transposition trees, and several extremal problems on the (minimum and/or maximum) size of graphs under a given graph property.

The thesis includes six chapters. The first one is to introduce definitions and summary the main results of the thesis, and in the last chapter we introduce the furture research of the thesis. The main studies in Chapters 2 - 5 are as follows.

In Chapter 2, we explore conditions for a graph to be supereulerian.

In Section 1, we characterize the graphs with minimum degree at least 2 and matching number at most 3. By using the characterization, we address a conjecture of Lai and Yan.

In Section 2 of Chapter 2, we prove that if $d(x)+d(y)geq n-1-p(n)$ for any edge $xyin E(G)$, then $G$ is collapsible except for several special graphs, where $p(n)=0$ for $n$ even and $p(n)=1$ for $n$ odd. As a corollary, a characterization for graphs satisfying $d(x)+d(y)geq n-1-p(n)$ for any edge $xyin E(G)$ to be supereulerian is obtained. This result extends the result in cite{catlinspanning}.

In Section 3 of Chapter 2, we focus on a conjecture posed by Chen and Lai~[Conjecture~8.6 of cite{chenlai}] that every 3-edge connected and essentially 6-edge connected graph is collapsible. We find a kind of sufficient conditions for a 3-edge connected graph to be collapsible.

In Chapter 3, we mainly consider the hamiltonicity of 3-connected line graphs.

In the first section of Chapter 3, we give several conditions for a line graph to be hamiltonian, especially we show that every 3-connected, essentially 11-connected line graph is hamilton-connected.

In the second section of Chapter 3, we show that every 3-connected, essentially 10-connected line graph is hamiltonian-connected.

In the third section of Chapter 3, we show that 3-connected, essentially 4-connected line graph of a graph with at most 9 vertices of degree 3 is hamiltonian. Moreover, if $G$ has 10 vertices of degree 3 and its line graph is not hamiltonian, then $G$ can be contractible to the Petersen graph.

In Chapter 4, we consider edge fault-tolerant hamiltonicity of Cayley graphs generated by transposition trees. We first show that for any $Fsubseteq E(Cay(B:S_{n}))$, if $|F|leq n-3$ and $ngeq 4$, then there exists a hamiltonian path in $Cay(B:S_{n})-F$ between every pair of vertices which are in different partite sets. Furthermore, we strengthen the above result in the second section by showing that $Cay(S_n,B)-F$ is bipancyclic if $Cay(S_n,B)$ is not
a star graph, $ngeq4$ and $|F|leq n-3$.

In Chapter 5, we consider several extremal problems on the size of graphs.

In Section 1 of Chapter 5, we bounds the size of the subgraph induced by $m$ vertices of hypercubes. We show that a subgraph induced by $m$ (denote $m$ by $sumlimits_{i=0}^{s}2^{t_i}$, $t_0=[log_2m]$ and $t_i=[log_2({m-sumlimits_{r=0}^{i-1}2^{t_r}})]$ for $igeq1$) vertices of an $n$-cube (hypercube) has at most $sumlimits_{i=0}^{s}t_i2^{t_i-1}+sumlimits_{i=0}^{s} icdot 2^{t_i}$ edges. As its applications, we determine the $m$-extra edge-connectivity of hypercubes for $mleq 2^{[frac{n}2]}$ and $g$-extra-edge-connectivity ($lambda_g(FQ_n)$) of the folded hypercube $FQ_n$ for $gleq n$.

In Section 2 of Chapter 5, we partially study the minimum size of graphs with a given minimum degree and a given edge degree. As an application, we characterize some kinds of restricted edge connected graphs with minimum edge number.

In Section 3 of Chapter 5, we consider the minimum size of graphs satisfying Ore-condition.

Ph.D. dissertations & Faculty habilitations


Creative work has been at the core of research in Human-Computer Interaction (HCI). I describe the results of a series of studies that look at how creators work, where creators include artists with years of professional practice, as well as learners, or novices and casual makers. My research focuses on three creation activities: drawing, physical modeling, and music composition. For these activities, I examine how artists switch between representations and how these representations evolve throughout their creative process, from early sketches to fine-grained forms or structured vocabularies. I present interactive systems that enrich their workflow (i) by extending their computer tools with physical user interfaces, or (ii) by making physical materials interactive. I also argue that sketch-based representations can allow for user interfaces that are more personal and less rigid. My presentation will reflect on lessons and limitations of this work and discuss challenges for future design-support tools.