Étude de la conjecture de Seymour sur le second voisinage

Soit D un digraphe simple (sans cycle orienté de longueur 2 ). En 1990, P. Seymour a conjecturé que D a un sommet v avec un second voisinage extérieur au moins aussi grand que son (premier) voisinage extérieur [1]. 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 spécial plus faible (mais important) de la conjecture de Caccetta et Häggkvist [2] proposé en 1978 : tout digraphe D avec un degré extérieur minimum au moins égale à jV (D)j=k a un cycle orienté de longueur au plus k. Le cas particulier est k = 3, et le cas faible exige les deux : le degré extérieur minimum et le degré intérieur minimum de D sont au moins égaux à jV (D)j=k. La conjecture de Seymour restreinte au tournoi est connue sous le nom de conjecture de Dean [1]. En 1996, Fisher [3] a prouvé la conjecture de Dean en utilisant un argument de probabilité. En 2003, Chen, Shen et Yuster [4] ont démontré que tout digraphe a un sommet v tel que d+(v) _ d++(v) où =0.657298..... est l'unique racine de l'équation 2x3 + x2 - 1 = 0. En 2000, Havet et Thomassé [5] ont donné une preuve combinatoire de la conjecture de Dean, en utilisant un outil appelé l'ordre médian. Ils ont démontré que le dernier sommet d'un tel ordre a toujours un second voisinage extérieur au moins aussi grand que son voisinage extérieur. En 2007, Fidler et Yuster [6] ont utilisé l'ordre médian et un autre outil qui s'appelle le digraphe de dépendance afin de prouver la conjecture de Seymour pour tout digraphe D ayant un degré minimum jV (D)j 2. Ils l'ont montré pour tout tournoi où manque un autre sous-tournoi. El Sahili a conjecturé que pour tout D, il existe un completion T de D et un ordre médian de T tel que le denier sommet a un second voisinage extérieur au moins aussi grand que son voisinage extérieur (EC). Il est clair que, EC implique SNC. Cependant, EC propose une méthode afin de résoudre la SNC. En général, on oriente les non arcs de D de manière appropriée, afin 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é désirée. Clairement, grâce aux résultats de [5] et [6], la EC est valable pour tournoi, et tout tournoi où manque un autre sous-tournoi. Nous allons vérifier EC pour tout digraphe D ayant un degré minimum jV (D)j 2. Alors, EC est vraie pour tout digraphe où la SNC est déjà connue d'être vraie non trivialement. Nous sommes aussi intéressés à la version pondérée de SNC et EC. En réalité, Fidler et Yuster [6] ont 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 afin de prouver la SNC pour tout digraphe D ayant un degré minimum1 jV (D)j 2. Nous allons définir le digraphe de dépendance de façon plus générale 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 méthode 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 où manque une étoile généralisée, soleil, étoile, ou un graphe complété. En outre, nous prouvons la EC, et par conséquent la SNC, pour digraphes où manque un peigne et digraphe où manque un graphe complet moins 2 arêtes indépendantes ou moins les arêtes d'une cycle de longueur 5. Par ailleurs, nous prouvons la EC, et par conséquent la SNC, pour les digraphes où 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 certains cas, on trouve au moins deux sommets avec la propriété désirée.