图上独立圈若干问题的结构参数（英文）

图书标准信息

• 作者 高云澍 编
• 出版社 科学出版社
• 出版时间 2020-06
• 版次 1
• ISBN 9787030649928
• 定价 128.00元
• 装帧 其他
• 开本 16开
• 页数 240页
• 字数 300千字

【内容简介】

¡¡¡¡The study of graph theory started over two hundreds years ago. The earliest known paper is due to Euler£¨1736£© about the seven bridges of Korugsberg. Since 1960s£¬ graph theory has developed very fast and numerous results on graph theory sprung forth. There are many nice and celebrated problems in graph theory£¬ such as Hamiltonian problem£¬ four-color problem£¬ Chinese postman problem£¬ etc. Moreover£¬ graph theory is widely applied in chemistry£¬ computer science£¬ biology and other disciplines. As a subfield in discrete mathematics£¬ graph theory has attracted much attention from all perspectives.
¡¡¡¡All graphs are considered only finite£¬ simple£¬ undirected graphs with no loops and no multiple edges. Let G be a graph. The Hamiltonian cycle problem is one of the most well-known problems in graph theory. A cycle which contains every vertex of G is called a Hamiltonian cycle. A cycle is called a chorded cycle if this cycle contains at least one chord. A k-factor in a graph G is a spanning k-regular subgraph of G£¬ where k is a positive integer. There exists many interesting results about the existence of k-factor£¬ by applying Tutte's Theorem£¬ however£¬ we mainly focus on the existence of 2-factor throughout this thesis. Clearly£¬ a Hamiltonian cycle is a 2-factor with exactly one component. From this point of view£¬ it is a more complex procedure to find the condition to ensure the existence of 2-factor in a given graph. The most usual technique to resolve 2-factor problems is to find a minimal packing and then extend it to a required 2-factor.
¡¡¡¡The book is concerned with structural invariants for packing cycles in a graph and partitions of a graph into cycles£¬ i.e.£¬ finding a prescribed number of vertex-disjoint cycles and vertex-partitions into a prescribed number of cycles in graphs. It is well-known that the problem of determining whether a given graph has such partitions or not£¬ is NP-complete. Therefore£¬ many researchers have investigated degree conditions for packing and partitioning. This book mainly focuses on the following invariants for such problems£º minimum degree£¬ average degree £¨also extremal function£©£¬ degree sum of independent vertices and the order condition with minimum degree.

【目录】