Ph.D
Group :
A contribution to the theory of (signed) graph homomorphism bound and Hamiltonicity
Starts on
Advisor :
Funding : Bourse pour étudiant étranger
Affiliation : vide
Laboratory :
Defended on 04/05/2016, committee :
Directeur de thèse :
M. Hao LI, Directeur de Recherche, CNRS Université Paris-Sud
Co-Directeur de thèse :
M. Reza NASERASR, Chargé de Recherche, CNRS Université Paris Diderot
Examinateurs :
Mme Liying KANG, Professor, Shanghai University
M. Yannis MANOUSSAKIS, Professor, Université ParisSud
Rapporteurs :
M. Éric SOPENA, Professor, Université de Bordeaux
M. Mariusz WOZNIAK, Professor, AGH University of Science and Technology
Research activities :
Abstract :
In this thesis, we study two main problems in graph theory: homomorphism problem of planar (signed) graphs and
Hamiltonian cycle problem.
As an extension of the Four-Color Theorem, it is conjectured that every planar consistent signed graph of unbalanced-girth $d+1(dgeq 2)$ admits a homomorphism to signed projective cube $SPC(d)$ of dimension $d$. It is naturally asked that:
Is $SPC(d)$ an optimal bound of unbalanced-girth $d+1$ for all planar consistent signed graphs of unbalanced-girth $d+1$?
In Chapter 2, we prove that: if $(B, Omega)$ is a consistent signed graph of unbalanced-girth $d$ which
bounds the class of consistent signed planar graphs of unbalanced-girth $d$, then $|B|geq 2^{d-1}$. Furthermore, if no subgraph of $(B, Omega)$ bounds the same class, $delta (B)geq d$, and therefore, $|E(B)|geq dcdot 2^{d-2}$. Our result shows that if the conjecture above holds, then the $SPC(d)$ is an optimal bound both in terms of number of vertices and number of edges.
When $d=2k$, the problem is equivalent to the homomorphisms of graphs: is $PC(2k)$ an optimal bound of odd-girth $2k+1$ for $mathcal{P}_{2k+1}$ (the class of all planar graphs of odd-girth at least $2k+1$) ? Note that $K_4$-minor free graphs are planar graphs, is $PC(2k)$ also an optimal bound of odd-girth $2k+1$ for all $K_4$-minor free graphs of odd-girth $2k+1$ ?
The answer is negative, in a manuscript, a family of graphs of order $mathcal{O}(k^2)$ bounding the $K_4$-minor free graphs of odd-girth $2k+1$ were given. Is this an optimal bound? In Chapter 3, we prove that: if $B$ is a graph of odd-girth $2k+1$ which bounds all the $K_4$-minor free graphs of odd-girth $2k+1$, then $|B|geq frac{(k+1)(k+2)}{2}$. Our result together with the result above shows that order $mathcal{O}(k^2)$ is optimal.
Furthermore, if $PC(2k)$ bounds $mathcal{P}_{2k+1}$, then $PC(2k)$ also bounds $mathcal{P}_{2r+1}$ $(r > k)$.
However, in this case we believe that a proper subgraph of $PC(2k)$ would suffice to bound$mathcal{P}_{2r+1}$,
then what's the optimal subgraph of $PC(2k)$ that bounds $mathcal{P}_{2r+1}$ ? The first case of this problem which is not studied is $k=3$ and $r=5$. For this case, Naserasr conjectured that the Coxeter graph bounds $mathcal{P}_{11}$.
Supporting this conjecture, in Chapter 4, we prove that the Coxeter graph bounds $mathcal{P}_{17}$.
In Chapters 5,6, we study the Hamiltonian cycle problems. Dirac showed in 1952 that every graph of order $n$ is
Hamiltonian if any vertex is of degree at least $frac{n}{2}$. This result started a new approach to develop sufficient conditions on degrees for a graph to be Hamiltonian. Many results have been obtained in generalization of Dirac's theorem.
In the results which strengthen Dirac's theorem, there is an interesting research area: to control the placement of a set of vertices on a Hamiltonian cycle such that these vertices have some certain distances among them on the Hamiltonian cycle.
In this thesis, we consider two related conjectures, one is given by Enomoto: if $G$ is a graph of order $ngeq 3$ and $delta(G)geq frac{n}{2}+1$, then for any pair of vertices $x$, $y$ in $G$, there is a Hamiltonian cycle $C$ of $G$ such that $dist_C(x,y)=lfloor frac{n}{2}rfloor$. Motivated by this conjecture, it is proved that a pair of vertices are located at distances no more than $frac{n}{6}$ on a Hamiltonian cycle. Considering the cases $delta(G)geq frac{n+k}{2}$, $2leq kleq frac{n}{2}$, Faudree and Li proved that a pair of vertices can be located at any given distance from $2$ to $k$ on a Hamiltonian cycle. Moreover, Faudree and Li proposed a more general conjecture: if $G$ is a graph of order $ngeq 3$ and $delta(G)geq frac{n}{2}+1$, then for any pair of vertices $x$, $y$ in $G$ and any integer $2leq k leq frac{n}{2}$,
there is a Hamiltonian cycle $C$ of $G$ such that $dist_C(x,y)= k$.
Using Regularity Lemma and Blow-up Lemma, in Chapter 5, we give a proof of Enomoto's conjecture for graphs of sufficiently large order, and in Chapter 6, we give a proof of Faudree and Li's conjecture for graphs of sufficiently large order.
