Dissertation > Excellent graduate degree dissertation topics show

# The New Lower Bound of the Number of Vertices of Degree 5 and Trivially Noncontractible Edges in Contraction Critical 5 Connected Graphs

Author: LiZuoZuo
Tutor: SuJianJi；YuanXuDong
School: Guangxi Normal University
Course: Applied Mathematics
Keywords: contraction critical 5 connected fragments trivially noncontractible edges
CLC: O157.5
Type: Master's thesis
Year: 2007
Downloads: 7
Quote: 0
Read: Download Dissertation

### Abstract

 An edge of a k connected graph is said to be k contractible if the contraction of this edge resultsin a k connected graph. It is known that every 3 connected graph of order 5 or more contains a 3contractible edge. By using this fact, in 1980, Thomassen（[1]） proved three Kuratowski’s theoremsabout planar graph by induction. So, the existence of k contractible edges in a k connected graphplays an vital role in proving some properties of a graph by induction. From then on, a lot of studyof k contractible edges in k connected graph have been down（J2] [3] [4][5]）. If G does not have any kcontractible edge, then G is called contractible critical k connected. In order to get some conditionsof having a contractible edge in a k connected graph, it is natural to study the contraction criticalk connected graph.Egawa（[6]） proved that every contraction critical k connected graph has a fragment withcardinality at most k/4. So, for k=4, 5, 6, 7, every contraction critical k connected graph contains avertex of degree k. It is known that there are not contraction critical 3 connected graphs of order 5or more（[7]）, and there are only two special classes for contraction critical 4 connected graph: thesquare of a cycle or the line graph of a cyclically 4 connected 3 regular graph（[8][9]）. Then it isnatural to study the structure of contraction critical 5 connected graph, this problem appears verydifficult, and also attracted many people’s attention. In order to study the structure of contractioncritical 5 connected graph, we firstly try to study some properties of contraction critical 5 connectedgraph. From the result of Egawa we have known that every contraction critical 5 connected graphhas at least a vertex of degree 5. For the distribution of vertices of degree 5 in contraction critical5 connected graph, in 1994, Yuan Xudong obtained that:Theorem A（[10]） Let G be a contraction critical 5 connected graph. Then any vertex of Gis adjacent to a vertex of degree 5.By Theorem A, we can deduce that any contraction critical 5 connected graph G has at least1/5|G| vertices of degree 5. Later Sudianji improved Theorem A by:Theorem B（[11]） Let G be a contraction critical 5 connected graph. Then any vertex of Gis adjacent to two vertex of degree 5.By Theorem B, we can deduce that any contraction critical 5 connected graph G has at least2/5|G| vertices of degree 5. Recently QinCheng fu proved that:Theorem C（[12]） Let G be a contraction critical 5 connected graph. Then |V5（G）|≥4/9|V（G）|. In this paper, we obtain the further result:Theorem 1 Let G be a contraction critical 5 connected graph. Then G has at least 1/2|G|vertices of degree 5.For contraction critical k connected graph G, Thomassen（[1]） proved that G has a triangle,later Mader（[13]） proved that G has at least 1/3|G| triangles. Recently, Kriesell（[14]） proved thatG contains at least 2/3|G| triangles. As contraction critical 5 connected graph has lots of trianglesand vertices of degree 5, it also has lots of triangles through vertices of degree 5. An edge of a kconnected graph is said to be trivially noncontractible if its end vertices have a common neighborof degree k. Ando proved that:Theorem D（[15]） Each contraction critical 5 connected graph of order n has at least n/2trivially noncontractible edges.And he put forward the following conjecture:Conjecture Each contraction critical 5 connected graph of order n has at least 2n triviallynoncontractible edges.Recently, LiXiangjun proved that:Theorem E（[16]） Any contraction critical 5 connected graph G has at least |G|+1 triviallynoncontractible edges.By using Theorem E, here we obtain the further result:Theorem 2 Let G be a contraction critical 5 connected graph. Then G has at least 3/2|G|trivially noncontractible edges.

### Related Dissertations

CLC: > Mathematical sciences and chemical > Mathematics > Algebra,number theory, portfolio theory > Combinatorics ( combinatorics ) > Graph Theory
© 2012 www.DissertationTopic.Net  Mobile