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

  1. Micro- grid with distributed power control strategy research,TM61
  2. The Grid-Connected Wind-solar Hybrid Generation System and Maximum Power Point Tracking,TM61
  3. Single phase photovoltaic grid-connected inverter control technology research,TM464
  4. The Research on Distributed Self-Organized Network Based Wide Area Backup Protection,TM774
  5. Research & Design of Three-Phase PV Grid-connected Inverter,TM464
  6. More autonomous vehicle sensor network information transmission Optimal Allocation,TN929.5
  7. Solder paste printing quality based on image processing techniques to detect,TP391.41
  8. The Research on Methods of Gene Co-expression Network Analysis of Sleep Deprivation,Q41
  9. The Study of Some Types of Domination Parameters of Graphs,O157.5
  10. Research on the New Method of MPPT and Islanding Detection in Pv Grid-connected Power Generation System,TM614
  11. Small wind power system power quality control,TM614
  12. Research on MPPT Strategy Applied of Single-stage Grid-connected Photovoltaic System,TM464
  13. Equalization Controling Systems for Series Connected Energy Storage Cells Based on Three-Cell Direct Equalization Circuit,TM910
  14. The Research of 10 KW Three-phase Photovoltaic Grid-connected Inverter,TM464
  15. Research on DSP-based Three-Phase Wind Power Grid-connected Inverter,TM614
  16. Research on Solar Photovoltaic Cell Converter,TM914.4
  17. Control Strategies of Power Quality Composite Conditioner and Studies of the Technology Connected with Power System,TM761
  18. Design of Grid-Connected Solar Photovoltaic System and Research on Effect of PV on Power Grid,TM615
  19. Study on the Annual Dynamic Energy Consumption of Multi-Connected Air-Condition System,TU831.3
  20. The Research on Connection Transaction Legal Supervision System of Our Country,D922.28
  21. Development and Application of Can Bus for RH6000 Control System,TP273.5

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