Dissertation > Excellent graduate degree dissertation topics show

The Polynomial Modeling and Grobner Basis Solving of Several Problems in Graph Theory

Author: XiongXueZuo
Tutor: LiHuiShi
School: Hainan University
Course: Applied Mathematics
Keywords: graph k-independent maximal independent k-covering minimum covering k-matchings maximal matchings perfect matchings backbone k-coloring backbone chromaticnumber k-total coloring minimal total coloring total chromatic number Strong coloring k-Strong coloring Strong chromatic number (k,d)-coloring Grobner bases
CLC: O157.5
Type: Master's thesis
Year: 2012
Downloads: 23
Quote: 0
Read: Download Dissertation

Abstract


This thesis is devoted to an algebraic study of the following problems in graph theory:1. The problem of independent set;2. The problem of covering;3. The problem of matching and perfect matching;4. The problem of backbone coloring;5. The problem of total coloring;6. The problem of strong coloring;7. The problem of (k,d)-coloring. Comparing to the already existed study of the same problems in the literature, where most of the results are either seeking the maximal or minimal solutions by means of a certain optimization method or restricted to some special types of graphs, we solve the listed problems by introducing, for an arbitrary finite graph G and a positive integer k, the k-counting problem with respect to the problems in1-7respectively, that is, the problem of k-independent set; the problem of k-covering; the problem of k-matching; the problem of k-backbone coloring; the problem of k-total coloring; the problem of k-strong coloring; and the problem of (k, d)-coloring. The main results we obtained are:●A mathematical model for each k-counting problem is given by a system of polynomial equations;●An effective criterion for checking the existence of solutions to the k-counting models is given in terms of Grobner basis method;●In the case that a k-counting model has a solution, the Grobner basis method for finding all solutions is given;●A maximal or minimal solution, or an invariant (e.g. chromatic number) asked by a k-counting model may be found among the solutions obtained in the last step.Since the polynomial models we constructed are independent of the types and size of the given graphs, and since nowadays Grobner basis method has been a well-developed, powerful and efficient method in solving system of polynomial equations on computer, the results obtained in this thesis are not only effective in solving the foregoing problems for each arbitrarily given graph, helpful in examining some important conjectures (for instance, the total coloring conjecture), but also provides a feasible theoretical foundation for the polynomial modeling and Grobner basis solving of certain similar discrete mathematical problems.

Related Dissertations

  1. Research on Graph-Based Algorithm for Tagsnps Selection,Q78
  2. Investigation on Microstructure and Properties of Cadmium-Free Silver-Based Intermediate Temperature Filler Metals,TG425.2
  3. Reseach on Optimal Control of Elevator Group Based upon Ant Colony Algorithm,TU857
  4. Compensation Methods of Different Speech Coding for Speaker Recognition,TN912.34
  5. Research on Decoding Algorithm for LDPC Codes,TN911.22
  6. Research on Parallel Frequent Graph Pattern Mining,TP311.13
  7. Fault Diagnosis Method Based on Support Vector Machine,TP18
  8. On the Consummation of Corporation Personality Denial Legal Regime in Our Country,D922.291.91
  9. The Research of General Education in Independent Institute,G642.3
  10. The Junior Middle School Language Teaching Text Analysis on the Cultivation of Autonomous Learning Ability,G633.3
  11. Analysis on the Effect of Moral Education Curriculum of the Independent College under the Network Circumstances,G641
  12. Algebraic Conditions and Dynamical Properties of the Seven Dimensional Stably Dissipative Systems,O175
  13. The Criticism on S-O-R Model and the Research on Anticipation Effect,B841
  14. Research on the Construction of Self-class,G424.21
  15. Study of Data Reduction Technique Based on Manifold Learning,TP311.13
  16. Effect of Turning ,covering Techniques and Season on Trough Composting,S141.4
  17. The Study on How Teachers Guide Senior Students to Carry Out Their Independent Reading in the Course of Reading Teaching,G633.3
  18. The Comparative Research on Readers’ Reading Tendency of Different Type University Libraries in Digital Time,G258.6
  19. The Investigation of Promotion Models of China’s Independent Costume Designer’s Brands,TS941.2
  20. Based on \,G804.49
  21. Multi-attribute undirected weighted graph clustering method,O157.5

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