Etude de quelques invariants de graphes

الموضوعات

علوم بحتة وطبيعية

الملخص

L'objet principal de cette thèse est l'étude de quelques aspects théoriques des problèmes liés à la théorie de la domination dans les graphes. Un sous-ensemble S de sommets d'un graphe G=(V,E) est dit dominant si tout sommet de V−S est adjacent à au moins un sommet de S. Le nombre de domination γ(G) est le cardinal minimum d'un ensemble dominant de G. La détermination de γ(G) dans un graphe quelconque est extrêmement difficile. Plusieurs types de domination sont définis en imposant des propriétés supplémentaires sur les ensembles dominants, citons la domination stable, double et couplée dont les paramètres associés sont désignés respectivement par i(G), γ×2(G ) et γpr(G ). On commence par établir une nouvelle borne supérieure pour i(G) améliorant la célèbre et vieille borne de Claude Berge établie pour γ(G). Ensuite on caractérise les arbres extrémaux atteignant la borne pour les deux paramètres ainsi qu'une caractérisation des graphes réguliers atteignant la borne sur γ(G). D'autres résultats sont obtenus en conséquence de cette nouvelle borne pour la somme et le produit des paramètres de domination inférieurs et le nombre chromatique d'un graphe. On entame par la suite l'étude de la domination double où on établit une condition nécessaire et suffisante pour la minimalité (au sens de l'inclusion) des ensembles dominants doubles ainsi que divers bornes sur γ×2(G), en particulier dans le cas des arbres, suivies par des caractérisations des arbres extrémaux. On initie l'étude de la domination double exacte dans les graphes. On montre que le problème d'existence d'un ensemble dominant double exact est NP-complet en général et nous caractérisons par construction les arbres admettant de tels ensembles. Concernant la domination couplée, nous citons en particulier une caractérisation par construction des arbres admettant un ensemble dominant couplé minimum unique. Nous montrons que γ×2(G)≥γpr(G) si G est sans griffes ou bien un arbre non trivial et nous caractérisons les arbres extrémaux pour l'égalité.

روابط وملفات

التعريف والنوع

رقم الوثيقة

0cd782ef-381d-4a48-b8ce-e2bf31c3f98c

رقم العقد

0

نوع الوسائط

Crawler

نوع المحتوى

الرسائل العلمية

صيغة المصدر

رسائل دكتوراة

نوع الملف

pdf text

أسماء الملفات

1377017_1.pdf

بيانات النشر

ألقاب المؤلفين

[{"name_ar":" Mustapha Chellali","title_ar":"اعداد","title_en":"Preparation"},{"name_ar":"Abdelkader Khelladi ","title_ar":"اشراف","title_en":"Supervision"}]

اللغة

French

المصدر والدورية

اسم المصدر

Etude de quelques invariants de graphes

المحتوى والصفحات

عدد الصفحات

0

كلمات الباحثين

Graphes, Recherche opérationnelle

إشراف وإعداد

الإشراف

Abdelkader Khelladi

الإعداد

Mustapha Chellali

الاقتباسات الببليوغرافية