More Website Templates @ TemplateMonster.com. July 16, 2012!

 
 
 
 

Thèses Soutenues

 

  Titre de la thèse

Etude de la Conjecture de Seymour sur le Second Voisinage

     
  Auteur(s) Salman GHAZAL
     
  Laboratoires

 

     
  Thèse en cotutelle

UNIVERSITE LIBANAISE
Ecole Doctorale des Sciences et de Technologie
UNIVERSITE CLAUDE BERNARD LYON 1

     
  TheseEDLiban.pdf
     
  Titre Etude de la Conjecture de Seymour sur le Second Voisinage
     
  Titre en englais
A Study of Seymour's Second Neighborhood Conjecture
     
  Date de soutenance

15 Decembre 2011

     
  Résumé
Soit D un digraphe simple (sans cycle oriente de longueur 2 ). En 1990, P. Seymour a conjecture que D a un sommet v avec un second voisinage exterieur au moins aussi grand que son (premier) voisinage exterieur [14].
Cette conjecture est connue sous le nom de la conjecture du second voisinage du Seymour (SNC). Cette conjecture, si elle est vraie, impliquerait, un cas special plus faible (mais important) de la conjecture de Caccetta et Haggkvist [11] propose en 1978: tout digraphe D avec un degre exterieur minimum au moins egale €„„à jV (D)j=k a une cycle oriente de longueur au plus k. Le cas particulier est k = 3, et le cas faible exige les deux: le degre exterieur minimum et le degre interieur minimum de D sont au moins egaux
€„„à jV (D)j=k. La conjecture de Seymour restreinte au tournoi est connue sous le nom de conjecture de Dean [14]. En 1996, Fisher [4] a prouve la conjecture de Dean en utilisant un argument de probabilite. En 2003, Chen, Shen et Yuster [8] ont demontre que tout digraphe a un sommet v tel que d+(v)  d++(v) ou =0.657298..... est l'unique racine
de l'equation 2x3 + x2 􀀀 1 = 0.
En 2000, Havet et Thomasse [7] ont donne une preuve combinatoire de la conjecture de Dean, en utilisant un outil appele l'ordre median. Ils ont demontre que le dernier sommet d'un tel ordre a toujours un second voisinage exterieur au moins aussi grand que son voisinage extérieur.
En 2007, Fidler et Yuster [3] ont utilisé l'ordre médian et une autre outil qui s'appelle le digraphe de dépendance a n de prouver la conjecture de Seymour pour tout digraphe D ayant un degre minimum jV (D)j 􀀀 2. Ils l'ont montre pour tout tournoi ou manque un autre sous-tournoi.
El Sahili a conjecture que pour tout D, il exist un completion T de D et un ordre median de T tel que le denier sommet a un second voisinage exterieur au moins aussi grand que son voisinage exterieur (EC). Il est clair que, EC implique SNC. Cependant, EC propose une methode pour a n de resoudre la SNC. En général, on orient les non arcs de D en maniere appropriée, a n d'obtenir un tournoi T et on essaie de trouver un sommet particulier (le denier sommet d'un ordre médian) avec la propriété desirée.
3 Clairement, grace aux resultats de [7] et [3], la EC est valable pour tourni, et tout tournoi ou manque un autre sous-tournoi. Nous allons véri er EC pour tout digraphe D ayant un degré minimum jV (D)j 􀀀 2. Alors, EC est vraie pour tout digraphe ou la SNC est déj€„„à connue d'^etre vraie non
trivialement. Nous sommes aussi intéressé €„„à la version pondérée de SNC et EC. En réalité, Fidler et Yuster [3] utilisé les digraphes de dépendance comme un outil supplémentaire et le fait que la SNC pondérée est vraie pour les tournois a n de prouver la SNC pour tout digraphe D ayant un degre minimum jV (D)j 􀀀 2.
Nous allons de nir le digraphe de dependance de facon plus generale et qui convient €„„à n'importe quel digraphe. Nous allons utiliser le digraphe de dépendance et l'ordre médian comme des outils dans nos contributions €„„à cette conjecture.
Suivant la methode proposée par la EC, nous démontrons la version pondérée de EC, et par conséquent la SNC, pour les classes des digraphes suivants : Digraphes ou manque une étoile généralisée, soleil, étoile, ou
un graphe complete. En outre, nous prouvons la EC, et par conséquent la SNC, pour digraphes ou manque un peigne et digraphe ou manque un graphe complet moins 2 ar^etes indépendantes ou moins les ar^etes d'une cycle
de longueur 5. Par ailleurs, nous prouvons la EC, et par conséquent la SNC, pour les digraphes ou manque n étoiles disjointes, sous certaines conditions sur les deux degrés minimum du digraphe de dépendance. Des conditions plus faible sont exigées dans le cas n = 1; 2; 3. Dans certaines cas, on trouve au moins deux sommets avec la propriété désirée.
     
  Résumé en anglais

Let D be a digraph without digons (directed cycles of length 2). In 1990, Seymour [14] conjectured that D has a vertex whose rst out-neighborhood is at most as large as its second out-neighborhood. Such a vertex is said to have the second neighborhood property (SNP). This conjecture is known as
the second neighborhood conjecture (SNC). This conjecture, if true, would imply a weakening of a particular case (but important) of a long standing conjecture proposed by Caccetta and Haggkvist in 1978, which states that every digraph D with minimum out-degree at least jV (D)j=k has a directed cycle of length at most k. The special case is when k = 3 and the weakening requires both minimum out-degree and minimum in-degree at least jV (D)j=k [11].
Seymour's conjecture restricted to tournaments is known as Dean's conjecture [14]. In 1996, Fisher [4] gave a probabilistic proof to Dean's conjecture. In 2003 Chen, Shen and Yuster [8] proved that every digraph contains a vertex v such that d+(v)  d++(v), where = 0:657298::: is the unique real root of the equation 2x3 + x2 􀀀 1 = 0. In 2000, another proof of Dean's conjecture was given by Havet and Thomassé using a tool called median order [7]. They proved that the last vertex of this order, called a feed vertex, has second out-neighborhood at least as large as its rst out-neighborhood. Median order is found to be a useful tool not only for the class of tournaments but for other classes of digraphs.
In 2007, Fidler and Yuster [3] used also median orders to prove Seymour's conjecture for the class of digraphs with minimum degree jV (D)j􀀀2 (i.e. D is a digraph missing a matching) and tournaments minus another 5 subtournament.
El Sahili conjectured that for every digraph D there is a completion T of D and a median order of T whose feed vertex has the SNP in D. Clearly, El Sahili's conjecture (EC) implies SNC. However, as one can observe, EC suggests a method (an approach) for solving the SNC, which we will call the completion approach. In general, following this approach, we orient the missing edges of D in some 'proper' way, to obtain a tournament T. Then we consider a particular feed vertex (clearly, it has the SNP in T) and try to prove that it has the SNP in D as well. Clearly, the result of Havet and Thomassé shows that EC is true for tournaments and the result of Fidler
and Yuster [3] shows that EC holds for tournaments minus another subtournament.
We will verify EC for the class of tournaments missing a matching. So EC is veri ed for all the classes of digraphs where the SNC is known to hold non trivially. We will be interested also in the weighted version of EC and SNC. In reality, Fidler and Yuster [3] used dependency digraphs as a
supplementary tool for proving the SNC for digraphs missing a matching and the fact that the weighted SNC holds for tournaments.
We de ne dependency digraphs in a more general way, which is suitable to any digraph, and use them in our contribution to Seymour's conjecture. We also use the median order as a tool in our contribution. Using these two tools, and following the completion approach, we prove the weighted version of EC, and consequently the SNC, for several classes of digraphs: Digraphs missing a generalized star, sun, star or a complete graph. In addition, we prove EC, and consequently the SNC for digraphs missing a comb, and digraphs whose missing graph is a complete graph minus two independent edges or the edges of a cycle of length ve. Moreover, we prove it for digraphs missing n disjoint stars under some conditions. Weaker conditions are required for n = 1; 2; 3. In some cases, we exhibit at least two vertices with the SNP.

     
  Organisme de delivrance UNIVERSITE LIBANAISE
Ecole Doctorale des Sciences et de Technologie
UNIVERSITE CLAUDE BERNARD LYON 1
     
  Ecole doctorale Ecole Doctorale des Sciences et de Technologie
     
  Langue Francais
     
  Directeur de thèse
 
Prof. EL SAHILI Amine
Prof BROCHET Jean-Michel
     
  Composition du Jury

Président: H.KHEDDOUCI, Membres: Y.BOUDABBOUS, F.HAVET, K.KHURI-MAKDISI, M.KOUIDER, A.EL-SAHILI, B.MRAD, A-K.ISSAM

     
  Mots clés graphe, digraphe, tournoi, voisinage, second voisinage, degrés, chemin, cycle, arbre, étoile, ordre médian, digraphe de dépendance.
     
  Mots clés en anglais

graph, digraph, tournament, neighborhood, second neigh- borhood, degrees, path, cycle, tree, star, median order, dependency digraph.