作者：董九英
页数：112
出版社：科学出版社
出版日期：2019
ISBN：9787030598691
电子书格式：pdf/epub/txt
内容简介
本书《图的彩虹连通数与参数》共分为六章，研究彩虹连通数与图中参数的关系。靠前章引言包含了彩虹连通数的基本概念和基本结果。第二章写得是计算彩虹连通数的复杂性，从而说明了计算一个图的彩虹连通数是NP-困难的，确定一个给定的颜色使图彩虹连通是NP-接近的。第三章写得是图的彩虹连通数与很小度及很小度和的关系，图的点彩虹连通数与很小度及很小度和的关系。第四章写得是有桥图的彩虹连通数与半径的关系，无桥图的彩虹连通数与半径的关系。第五章写得是稠密图和稀疏图的彩虹连通数。第六章写得是彩虹连通数和独立数的关系。本书的每一章选取具有代表性的结果给与证明，证明中用到的方法可以用到其他类似结果的证明。每一章给读者提出未解决的问题和猜想
目录
Contents
Preface
Chapter 1 Introduction 1
1.1 Basic concepts 1
1.2 Basic results 5
Chapter 2 Rainbow Connection Number， Order and
Minimum Degree (sum) 14
2.1 Rainbow connection number， order and minimum degree (sum) 14
2.2 Rainbow vertex-connection number and minimum degree (sum) 27
Chapter 3 Rainbow Connection Number， Radius and Diameter 38
3.1 Rainbow connection number and radius with bridgeless 38
3.2 Rainbow connection number and radius with bridges 43
Chapter 4 Rainbow Connection Number and Independence
Number 52
4.1 Tight example 52
4.2 Lemma and observation 53
4.3 Theorem and proof 54
Chapter 5 Rainbow Connection Number of Dense， Sparse and
Random Graphs 69
5.1 Definitions of dense， sparse and random graphs 69
5.2 Rainbow connection number of dense graphs 69
5.3 Rainbow connection number of sparse and random graphs 74
Chapter 6 Computational Complexity 84
6.1 Conjecture of NP-hard and NP-complete 84
6.2 NP-hard and NP-complete 85
Reference 101
Index 106
Preface
Chapter 1 Introduction 1
1.1 Basic concepts 1
1.2 Basic results 5
Chapter 2 Rainbow Connection Number， Order and
Minimum Degree (sum) 14
2.1 Rainbow connection number， order and minimum degree (sum) 14
2.2 Rainbow vertex-connection number and minimum degree (sum) 27
Chapter 3 Rainbow Connection Number， Radius and Diameter 38
3.1 Rainbow connection number and radius with bridgeless 38
3.2 Rainbow connection number and radius with bridges 43
Chapter 4 Rainbow Connection Number and Independence
Number 52
4.1 Tight example 52
4.2 Lemma and observation 53
4.3 Theorem and proof 54
Chapter 5 Rainbow Connection Number of Dense， Sparse and
Random Graphs 69
5.1 Definitions of dense， sparse and random graphs 69
5.2 Rainbow connection number of dense graphs 69
5.3 Rainbow connection number of sparse and random graphs 74
Chapter 6 Computational Complexity 84
6.1 Conjecture of NP-hard and NP-complete 84
6.2 NP-hard and NP-complete 85
Reference 101
Index 106
