La K-domination et la K-indépendance dans les graphes

الموضوعات

علوم تطبيقية وتكنولوجية

الملخص

Soit G = (V; E) un graphe simple et k un entier positif. Un sous ensemble de sommets D dans le graphe G est dit k-dominant (resp. k-indépendant) si tout sommet extérieur à D a au moins k voisins dans D (resp. si le degré maximum du sous graphe induit par l’ensemble de sommets D est au plus k 1). La cardinalité minimum (resp. maximum) d’un ensemble k-dominant (resp. k-indépendant) de G est appelée le nombre de la k- domination (resp. le nombre de la k-indépendance) et est notée par k(G) (resp. k(G)). La détermination de ces deux paramètres dans les graphes en général est un problème difficile (NP-Complet).L’objectif principal de cette thèse est l’étude de ces deux paramètres et notre travail s’articule autour de trois axes, la détermination de bornes qui encadrent le plus possible ces paramètres, la caractérisation des graphes extrémaux et le statut ou l’état de chaque sommet vis-à-vis de ces deux paramètres. En effet, nous avons élaboré dans la première partie une généralisation d’une borne inférieure pour le paramètre k (G) déjà établie pour le nombre de 2-indépendance. Aussi on a fourni une caractérisation constructive des arbres extrémaux atteignant cette nouvelle borne pour k ≥ 2: Dans la deuxième partie nous avons donné la caractérisation des arbres tels que le nombre de 2-domination est égal au nombre de 2-indépendance. Dans la troisième partie, nous avons caractérisé les sommets appartenant à tout ou bien à aucun ensemble k-dominant minimum dans les arbres.

روابط وملفات

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

رقم الوثيقة

024a44f6-8645-4194-8d59-d4c7850df819

رقم العقد

0

نوع الوسائط

Crawler

نوع المحتوى

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

صيغة المصدر

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

نوع الملف

pdf text

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

2218434_1.pdf

بيانات النشر

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

[{"name_ar":"Mostafa Blidia","title_ar":"اشراف","title_en":"Supervision"},{"name_ar":"Nacéra Meddah","title_ar":"اعداد","title_en":"Preparation"}]

اللغة

French

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

اسم المصدر

La K-domination et la K-indépendance dans les graphes

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

عدد الصفحات

0

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

Graphes k-domination k-indépendance Arbres extrémaux

إشراف وإعداد

الإشراف

Mostafa Blidia

الإعداد

Nacéra Meddah

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