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
The original manuscript conceptualizes the recent rise of digital platforms along three main dimensions: their nature of coordination devices fueled by data, the ensuing transformations of labor, and the accompanying promises of societal innovation. The overall ambition is to unpack the coordination role of the platform and where it stands in the horizon of the classical firm – market duality. It is also to precisely understand how it uses data to do so, where it drives labor, and how it accommodates socially innovative projects. I extend this analysis to show continuity between today’s society dominated by platforms and the “organizational society”, claiming that platforms are organized structures that distribute resources, produce asymmetries of wealth and power, and push social innovation to the periphery of the system. I discuss the policy implications of these tendencies and propose avenues for follow-up research.