Arêtes suppressibles, cycles et connectivité / Haiyan Kang ; [sous la direction de] Mme Evelyne Flandrin [et de] M. Guojun Li

Date :

Editeur / Publisher : [s.l.] : [s.n.] , 2010

Type : Livre / Book

Type : Thèse / Thesis

Langue / Language : anglais / English

Théorie des graphes

Cycles

Prismes (géométrie)

Flandrin, Evelyne (Directeur de thèse / thesis advisor)

Liu, Guojun (19..-....) (Directeur de thèse / thesis advisor)

Université de Paris-Sud. Faculté des sciences d'Orsay (Essonne) (Autre partenaire associé à la thèse / thesis associated third party)

Université Paris-Sud (1970-2019) (Organisme de soutenance / degree-grantor)

Relation : Arêtes suppressibles, cycles et connectivité / Haiyan Kang ; [sous la direction de] Mme Evelyne Flandrin [et de] M. Guojun Li / Lille : Atelier national de reproduction des thèses , 2010

Résumé / Abstract : Soit G un graphe k-connexe et e = uv une arête de G. G/e nous noterons le graphe obtenu à partir de G en supprimant les sommets u, v et en ajoutant un nouveau sommet v_e tels que v_e est adjacent à tous les anciens voisins de u et v. Si G/e est encore k-connexe, e est appelé un bord de k-contractile. La première partie de la thèse étudie une propriété d'un bord contractile en k-connexe graphiques sans triangle. Soit G un graphe k-connexe, et soit e une arête de G. Soit GӨe désigner le graphe obtenu à partir de G par l'opération suivante: (1) supprimer e de G pour obtenir G-e; (2) pour tout sommet fin de e avec un degré k-1, disons x, x supprimer, puis ajouter des bordures entre toute paire de sommets non- adjacents dans N_ (G-e)(x). Si GӨe est k-connexe, e est dit être une arête suppressible de G. La deuxième partie de la thèse étudie la répartition des arêtes suppressibles dans les graphes 3-connexes ou des graphes 5-connexes. En outre, nous confirmons la conjecture Thomassen pour deux classes de graphes 3-connexes avec des limites de bords amovibles ou de descendre du cycle le plus long. La dernière partie de la thèse est consacrée à la cyclabilité prisme de graphiques. Le prisme de plus d’un graphe G est le produit cartésien GK_2 de la graphe G et K_2. Un graphe G est appelé hamiltonien prisme si le prisme de plus de G est hamiltonien. Nous disons qu'une série H V (G) de sommets est cyclable dans G s'il existe un cycle C de G contenant tous les sommets de H. Pour H V (G), on dit que H est cyclable prisme dans GK_2 si H ∪ H’ est cyclable dans GK_2 où H' est la copie de H. Nous prolongeons la suite Ozeki sur hamiltonicité prisme cyclabilité prisme de S. Il est également avancé pour les graphes sans griffe, la borne peut être réduite de 3 avec un expection.

Résumé / Abstract : Let G be a k-connected graph and e=uv an edge of G. By G/e we denote the graph obtained from G by deleting the vertices u,v and adding a new vertex v_e such that v_e is adjacent to all the former neighbors of u and v. If G/e is still k-connected, then e is called a k-contractible edge. The first part of the thesis studies a property of a contractible edge in k-connected triangle-free graphs. Let G be a k-connected graph, and let e be an edge of G. Let GӨe denote the graph obtained from G by the following operation: (1) delete e from G to get G-e; (2) for any end vertex of e with degree k-1, say x, delete x, and then add edges between any pair of non-adjacent vertices in N_{G-e}(x). If GӨe is k-connected, then e is said to be a removable edge of G. The second part of the thesis investigates the distribution of removable edges in 3-connected graphs or 5-connected graphs. In addition, we confirm Thomassen’s conjecture for two classes of 3-connected graphs with bounds of removable edges on or off a longest cycle. The last part of the thesis is devoted to the prism cyclability of graphs. The prism over a graph G is the Cartesian product GK_2 of G with the complete graph K_2. G is said to be prism hamiltonian if GK_2 is hamiltonian. We say that a set H V(G) of vertices is cyclable in G if there is a cycle C in G containing all vertices of H. For H V(G), we say that H is prism cyclable in GK_2 if H∪H' where H' is the copy of H is cyclable in GK_2. We extend Ozeki’s result on prism hamiltonicity to prism cyclability of S. It is also argued for claw-free graphs, the bound can be reduced 3 with one expection.