Dans cette thèse, nous concentrons sur les sujets suivants: super-eulérien graphe, hamiltonien ligne graphes, le tolerant aux pannes hamiltonien laceabilité de Cayley graphe généré par des transposition arbres et plusieurs problèmes extrémaux concernant la (minimum et/ou maximum) taille des graphes qui ont la même propriété.Cette thèse comprend six chapitres. Le premier chapitre introduit des définitions et indique la conclusion des resultants principaux de cette thèse, et dans le dernier chapitre, nous introduisons la recherche de furture de la thèse. Les travaux principaux sont montrés dans les chapitres 2-5 comme suit:Dans le chapitre 2, nous explorons les conditions pour qu'un graphe soit super-eulérien.Dans la section 1, nous caractérisons des graphes dont le dégrée minimum est au moins de 2 et le nombre de matching est au plus de 3. Dans la section 2, nous prouvons que si pour tous les arcs xy∈E(G), d(x)+d(y)≥n-1-p(n), alors G est collapsible sauf quelques bien définis graphes qui ont la propriété p(n)=0 quand n est impair et p(n)=1 quand n est pair.Dans la section 3 de la Chapitre 2, nous trouvons les conditions suffisantes pour que un graphe de 3-arcs connectés soit pliable.Dans le chapitre 3, nous considérons surtout l'hamiltonien de 3-connecté ligne graphe.Dans la première section de Chapitre 3, nous montrons que chaque 3-connecté, essentiellement11-connecté ligne graphe est hamiltonien-connecté. Cela renforce le résultat dans [91]. Dans la seconde section de Chapitre 3, nous montrons que chaque 3-connecté, essentiellement 10-connecté ligne graphe est hamiltonien-connecté.Dans la troisième section de Chapitre 3, nous montrons que 3-connecté, essentiellement 4-connecté ligne graphe venant d'un graphe qui comprend au plus 9 sommets de degré 3 est hamiltonien. Dans le chapitre 4, nous montrons d'abord que pour tous $F\subseteq E(Cay(B:S_{n}))$, si $|F|\leq n-3$ et $n\geq 4$, il existe un hamiltonien graphe dans $Cay(B:S_{n})-F$ entre tous les paires de sommets qui sont dans les différents partite ensembles. De plus, nous renforçons le résultat figurant ci-dessus dans la seconde section montrant que $Cay(S_n,B)-F$ est bipancyclique si $Cay(S_n,B)$ n'est pas un star graphe, $n\geq 4$ et $|F|\leq n-3$.Dans le chapitre 5, nous considérons plusieurs problems extrémaux concernant la taille des graphes.Dans la section 1 de Chapitre 5, nous bornons la taille de sous-graphe provoqué par $m$ sommets de hypercubes ($n$-cubes). Dans la section 2 de Chapitre 5, nous étudions partiellement la taille minimale d'un graphe savant son degré minimum et son degré d'arc. Dans la section 3 de Chapitre 5, nous considérons la taille minimale des graphes satisfaisants la Ore-condition. / In this thesis, we focus on the following topics: supereulerian graphs, hamiltonian line graphs, fault-tolerant Hamiltonian laceability of Cayley graphs generated by transposition trees, and several extremal problems on the (minimum and/or maximum) size of graphs under a given graph property. The thesis includes six chapters. The first one is to introduce definitions and summary the main results of the thesis, and in the last chapter we introduce the furture research of the thesis. The main studies in Chapters 2 - 5 are as follows. In Chapter 2, we explore conditions for a graph to be supereulerian.In Section 1 of Chapter 2, we characterize the graphs with minimum degree at least 2 and matching number at most 3. By using the characterization, we strengthen the result in [93] and we also address a conjecture in the paper.In Section 2 of Chapter 2, we prove that if $d(x)+d(y)\geq n-1-p(n)$ for any edge $xy\in E(G)$, then $G$ is collapsible except for several special graphs, where $p(n)=0$ for $n$ even and $p(n)=1$ for $n$ odd. As a corollary, a characterization for graphs satisfying $d(x)+d(y)\geq n-1-p(n)$ for any edge $xy\in E(G)$ to be supereulerian is obtained. This result extends the result in [21].In Section 3 of Chapter 2, we focus on a conjecture posed by Chen and Lai [Conjecture~8.6 of [33]] that every 3-edge connected and essentially 6-edge connected graph is collapsible. We find a kind of sufficient conditions for a 3-edge connected graph to be collapsible.In Chapter 3, we mainly consider the hamiltonicity of 3-connected line graphs.In the first section of Chapter 3, we give several conditions for a line graph to be hamiltonian, especially we show that every 3-connected, essentially 11-connected line graph is hamilton- connected which strengthens the result in [91].In the second section of Chapter 3, we show that every 3-connected, essentially 10-connected line graph is hamiltonian-connected.In the third section of Chapter 3, we show that 3-connected, essentially 4-connected line graph of a graph with at most 9 vertices of degree 3 is hamiltonian. Moreover, if $G$ has 10 vertices of degree 3 and its line graph is not hamiltonian, then $G$ can be contractible to the Petersen graph.In Chapter 4, we consider edge fault-tolerant hamiltonicity of Cayley graphs generated by transposition trees. We first show that for any $F\subseteq E(Cay(B:S_{n}))$, if $|F|\leq n-3$ and $n\geq4$, then there exists a hamiltonian path in $Cay(B:S_{n})-F$ between every pair of vertices which are in different partite sets. Furthermore, we strengthen the above result in the second section by showing that $Cay(S_n,B)-F$ is bipancyclic if $Cay(S_n,B)$ is not a star graph, $n\geq4$ and $|F|\leq n-3$.In Chapter 5, we consider several extremal problems on the size of graphs.In Section 1 of Chapter 5, we bounds the size of the subgraph induced by $m$ vertices of hypercubes. We show that a subgraph induced by $m$ (denote $m$ by $\sum\limits_{i=0}^ {s}2^{t_i}$, $t_0=[\log_2m]$ and $t_i= [\log_2({m-\sum\limits_{r=0}^{i-1}2 ^{t_r}})]$ for $i\geq1$) vertices of an $n$-cube (hypercube) has at most $\sum\limits_{i=0}^{s}t_i2^{t_i-1} +\sum\limits_{i=0}^{s} i\cdot2^{t_i}$ edges. As its applications, we determine the $m$-extra edge-connectivity of hypercubes for $m\leq2^{[\frac{n}2]}$ and $g$-extra edge-connectivity of the folded hypercube for $g\leq n$.In Section 2 of Chapter 5, we partially study the minimum size of graphs with a given minimum degree and a given edge degree. As an application, we characterize some kinds of minimumrestricted edge connected graphs.In Section 3 of Chapter 5, we consider the minimum size of graphs satisfying Ore-condition.
| Identifer | oai:union.ndltd.org:theses.fr/2013PA112183 |
| Date | 27 September 2013 |
| Creators | Yang, Weihua |
| Contributors | Paris 11, Li, Hao |
| Source Sets | Dépôt national des thèses électroniques françaises |
| Language | English |
| Detected Language | English |
| Type | Electronic Thesis or Dissertation, Text, Image |
Page generated in 0.0024 seconds