Contribution à l'étude des graphes cubiques et des graphes gracieux
Institution:
Paris 11Disciplines:
Directors:
Abstract EN:
This thesis contains two distinct parts. The first part is concerned with cubic graphs and the second part with graceful graphs. A cubic graph is a simple graph that is to say without loops and multiple edges, regular 3-valent. A cyclically k-edge connected graph (with k≥2) is a connected graph such that if we remove any set of less than k edges then, either the new graph is connected, or disconnected and at most one component contains a cycle. We shall say that cubic graph H is obtained by removing an edge e of a cubic graph G, if H is obtained from G by deleting and suppressing the two vertices of degree 2 created by the deletion. An edge of a cyclically k-edge-connected cubic graph is said to be k-removable if the removal of this edge gives a cyclically k-edge-connected cubic graph. In this first part we study the notion of k-removable edge (k≥2). In particular, we show that the notion of 3 removability is useful to generalize know results and to study cycles though given vertices in planar 3 connected cubic graphs, and we give some new results concerning this problem. In this part we also give some new conjectures and using the notion of removability we prove that they are equivalent to some classical conjectures on cubic 3-connected graphs. The second part is concerned with graceful graphs and is mainly the contents of two papers published in international journals. We recall that a simple graph on n vertices and m edges is said to be graceful if there exists an injective numbering of vertices in set {1, …. , m} inducing a numbering of m edges from 1 to m (if xy is an edge, the number of xy is a-b where a is a number of x and b the number of y). In the first paper we prove that cycles with one chord are graceful. In the second paper we generalize the notion of graceful graphs.
Abstract FR:
Cette thèse comporte deux parties. La première est consacrée à l'étude des graphes cubiques et la seconde à celle des graphes gracieux. Un graphe cubique est un graphe simple, c'est-à-dire sans boucle ni arêtes multiples, régulier de degré trois. Un graphe cycliquement k-arête-connexe (k≥2), est un graphe tel que si l'on enlève un ensemble quelconque d'au plus k arêtes, ou bien on ne disconnecte pas le graphe, ou bien on le disconnecte et au moins deux des composantes connexes contiennent chacune des cycles. La suppression d'une arête d'un graphe cubique consiste à enlever cette arête et à "effacer" les deux sommets de degré 2 ainsi créés. On dira qu'une arête d'un graphe cubique cycliquement k-arête-connexe est k-suppressible si la suppression de cette arête donne un graphe qui est encore cycliquement k-arête-connexe. La partie de la thèse concernant les graphes cubiques porte essentiellement sur l'étude de la notion d'arête k-suppressible. On montre en particulier comment l'étude fine de la 3-suppressibilité permet de retrouver et même généraliser des résultats connus, et fournit un outil précis pour l'étude des cycles passant par des points donnés d'un graphe cubique 3-connexe, où l'on obtient des résultats nouveaux. On donne aussi dans cette première partie des formes équivalentes à des conjectures bien connues dans les graphes cubiques 3-connexes, et là également la notion de suppressiblité joue un rôle dans certaines preuves. La partie concernant les graphes gracieux est constituée essentiellement de deux articles publiés dans des revues internationales. Rappelons qu'un graphe simple de n sommets et rn arêtes est dit gracieux s'il existe une numérotation injective des sommets dans l'ensemble {0,1,. . . , m} induisant une numérotation des m arêtes de 1 à m en considérant la valeur absolue de la différence des numéros des sommets adjacents. On montre dans le premier article que les cycles n'ayant qu'une seule corde sont gracieux. Dans le second article, on généralise la notion de graphe gracieux en la reliant à des travaux préexistants.