Abstract FR:

Cette these est constituee de deux parties independantes. La premiere porte sur l'etude de quelques parametres de plongements entre les reseaux d'interconnexion ; cette theorie entre dans le cadre du parallelisme. Nous donnons des bornes superieures de la largeur de coupe des graphes shuffle-exchange et de bruijn, ameliorant ainsi les deux resultats qui etaient connus anterieurement. Notre methode est basee sur la notion de quotient de graphes. Le second resultat essentiel de cette premiere partie est la mise au point d'un modele permettant le calcul des dilatations et congestions des plongements entre deux graphes qui s'ecrivent sous forme de graphes composes. En application de notre modele, nous trouvons plusieurs resultats dont la plupart sont nouveaux et interessants. La deuxieme partie traite des problemes sur les degres generalises a savoir l'union de voisinages ou les sommes des degres d'un ensemble de sommets. Le premier resultat essentiel s'est traduit par un majorant de l'un de ces parametres en fonction de la stabilite, dans les graphes sans grande etoile induite, generalisant ainsi deux resultats partiels connus. De plus, nous donnons des proprietes sur cette borne qui nous ont permis d'obtenir des resultats generaux du type chvatal-erdos. La deuxieme tranche de cette meme partie porte sur l'etude des classes de graphes reguliers au sens des degres generalises. Nous caracterisons certaines de ces familles de graphes d'une part et generalisons des resultats connus dans ce domaine d'une autre part.