Ph.D
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-Saclay
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.
