This monograph is designed to be an in-depth introduction to domination in graphs. It focuses on three core concepts: domination, total domination, and independent domination. It contains major results on these foundational domination numbers, including a wide variety of in-depth proofs of selected results providing the reader with a toolbox of proof techniques used in domination theory. Additionally, the book is intended as an invaluable reference resource for a variety of readerships, namely, established researchers in the field of domination who want an updated, comprehensive coverage of domination theory; next, researchers in graph theory who wish to become acquainted with newer topics in domination, along with major developments in the field and some of the proof techniques used; and, graduate students with interests in graph theory, who might find the theory and many real-world applications of domination of interest for masters and doctoral thesis topics. The focused coverage also provides a good basis for seminars in domination theory or domination algorithms and complexity.
The authors set out to provide the community with an updated and comprehensive treatment on the major topics in domination in graphs. And by Jove, they’ve done it! In recent years, the authors have curated and published two contributed volumes: Topics in Domination in Graphs, © 2020 and Structures of Domination in Graphs, © 2021. This book rounds out the coverage entirely. The reader is assumed to be acquainted with the basic concepts of graph theory and has had some exposure to graph theory at an introductory level. As graph theory terminology sometimes varies, a glossary of terms and notation is provided at the end of the book.
Author(s): Teresa W. Haynes, Stephen T. Hedetniemi, Michael A. Henning
Series: Springer Monographs in Mathematics
Publisher: Springer
Year: 2023
Language: English
Pages: 654
City: Cham
Dedication
Preface
Contents
Chapter 1 In the Beginning: Roots of Domination in Graphs
1.1 Introduction
1.2 Basic Terminology
1.3 Origins
1.3.1 Defensive and Offensive Strategies of the Roman Empire
1.3.2 Chaturanga
1.3.3 Eight Queens Problem
1.3.4 Five Queens Problem
1.3.5 Queens Independent Domination Problem
1.3.6 Queens Total Domination Problem
1.3.7 Generalizations to Other Chess Pieces
1.4 Application Driven Origins
1.4.1 Radio Broadcasting
1.4.2 Computer Communication Networks
1.4.3 Sets of Representatives
1.4.4 School Bus Routing and Bus Stop Selection
1.4.5 Electrical Power Domination
1.4.6 Influence in Social Networks
1.4.7 Topographic Maps
1.4.8 Transporting Hazardous Materials
1.5 Early Chronology of Domination in Graph Theory
Chapter 2 Fundamentals of Domination
2.1 Introduction
2.2 Core Concepts
2.2.1 Independent Sets
2.2.2 Dominating Sets
2.2.3 Irredundant Sets
2.3 Parameters Suggested by the Definition of a Dominating Set
2.3.1 Total Dominating Sets
2.3.2 k-Dominating Sets
2.3.3 H-forming Dominating Sets
2.3.4 Perfect and Efficient Dominating Sets
2.3.5 Distance-k Dominating Sets
2.3.6 Fractional Domination
2.4 Equivalent Formulations of Domination
2.4.1 Pendant Edges in Spanning Forests
2.4.2 Enclaveless Sets
2.4.3 Spanning Star Partitions
2.4.4 Non-dominating Partitions
2.4.5 Total Domination and Splitting Graphs
2.4.6 Dominating Sets and (1, 4 : 3)-Sets
2.5 Domination in Terms of Perfection in Graphs
2.6 Ore’s Lemmas and Their Implications
Chapter 3 Complexity and Algorithms for Domination in Graphs
3.1 Introduction
3.2 Brief Review of NP-Completeness
3.3 NP-Completeness of Domination, Independent Domination, and Total Domination
3.3.1 NP-Completeness Results for Arbitrary Graphs
3.3.2 NP-Completeness Results for Bipartite Graphs
3.3.3 Summary of Complexity Results for Graph Families
3.4 A Representative Sample of Domination Algorithms for Trees
3.4.1 Minimum Dominating Set
3.4.2 Minimum Independent Dominating Set
3.4.3 Minimum Total Dominating Set
3.5 Early Domination Algorithms and NP-Completeness Results
3.6 Other Sources for Domination Algorithms and Complexity
Chapter 4 General Bounds
4.1 Introduction
4.2 Domination and Maximum Degree
4.2.1 Domination Number and Maximum Degree
4.2.2 Total Domination Number and Maximum Degree
4.2.3 Independent Domination Number and Maximum Degree
4.3 Domination and Order
4.3.1 Domination Number and Order
4.3.2 Total Domination Number and Order
4.3.3 Independent Domination Number and Order
4.4 Basic Relationships Among Core Parameters
4.5 Domination and Distance
4.6 Domination and Packing
4.7 Gallai Type Theorems
4.8 Domination and Matching
Chapter 5 Domination in Trees
5.1 Introduction
5.2 Domination in Trees
5.2.1 Domination Bounds in Trees
5.2.2 Domination Lower Bounds Involving the Number of Leaves
5.2.3 Slater Lower Bound on the Domination Number
5.2.4 Vertices in All or No Minimum Dominating Sets
5.2.5 Domination and Packing in Trees
5.3 Total Domination in Trees
5.3.1 Total Domination Bounds in Trees
5.3.2 Total Domination Bounds Involving the Number of Leaves
5.3.3 Vertices in All or No Minimum Total Dominating Sets in Trees
5.3.4 Unique Minimum Total Dominating Sets in Trees
5.3.5 Total Domination and Open Packing in Trees
5.4 Independent Domination in Trees
5.4.1 Independent Domination Bounds in Trees
5.4.2 Unique Minimum Independent Dominating Sets in Trees
5.5 Equality of Domination Parameters
5.5.1 (gamma, i)-trees
5.5.2 (gamma, gamma-t)-trees
5.5.3 Summary
Chapter 6 Upper Bounds in Terms of Minimum Degree
6.1 Introduction
6.2 Bounds on the Domination Number
6.2.1 Minimum Degree One
6.2.2 Minimum Degree Two
6.2.3 Minimum Degree Three
6.2.4 Minimum Degree Four
6.2.5 Minimum Degree Five
6.2.6 Minimum Degree Six
6.2.7 Minimum Degree Seven or Larger
6.3 Bounds on the Total Domination Number
6.3.1 Minimum Degree One
6.3.2 Minimum Degree Two
6.3.3 Minimum Degree Three
6.3.4 An Interplay with Transversals in Hypergraphs
6.3.5 Minimum Degree Four
6.3.6 Minimum Degree Five
6.3.7 Minimum Degree Six
6.3.8 A Heuristic Bound
6.4 Bounds on the Independent Domination Number
6.4.1 Minimum Degree One
6.4.2 Arbitrary Minimum Degree
6.4.3 Regular Graphs
6.5 Summary
Chapter 7 Probabilistic Bounds and Domination in Random Graphs
7.1 Introduction
7.2 Probabilistic Bounds
7.3 Domination in Random Graphs
7.4 Summary
Chapter 8 Bounds in Terms of Size
8.1 Introduction
8.2 Domination and Size
8.3 Total Domination and Size
8.4 Independent Domination and Size
8.5 Summary
Chapter 9 Efficient Domination in Graphs
9.1 Introduction
9.1.1 Efficient Dominating Sets
9.1.2 Efficient Total Dominating Sets
9.1.3 Perfect Dominating Sets
9.1.4 Examples
9.2 Efficient Domination
9.2.1 Efficient Graphs
9.2.2 Efficient Grid Graphs and Efficient Toroidal Graphs
9.2.3 Efficient Cube-connected Cycles
9.2.4 Efficient Vertex-transitive Graphs
9.2.5 Efficient Cayley Graphs
9.2.6 Efficient Circulant Graphs
9.2.7 Efficient Graphs with Efficient Complements
9.3 Efficient Total Domination
9.3.1 Total Efficient Trees
9.3.2 Total Efficient Grid Graphs
9.3.3 Total Efficient Cylindrical Graphs
9.3.4 Total Efficient Toroidal Graphs
9.3.5 Total Efficient Product Graphs
9.3.6 Total Efficient Circulant Graphs
9.4 Algorithms and Complexity of Efficient Domination
Chapter 10 Domination and Forbidden Subgraphs
10.1 Introduction
10.2 Domination and Forbidden Cycles
10.2.1 Domination Number
Forbidden 4- and 5-Cycles and Minimum Degree Two
Domination and Large Girth
10.2.2 Total Domination Number
Forbidden Induced 6-cycles and Minimum Degree Two
Forbidden 4- and 6-cycles and Minimum Degree Three
Forbidden 4-cycles and Minimum Degree Four
Total Domination and Large Girth
10.2.3 Independent Domination Number
Forbidden 4-cycles
Bipartite Graphs
Triangle-free Graphs
10.3 Domination in Claw-free Graphs
10.3.1 Domination and Independent Domination Numbers
10.3.2 Total Domination Number
10.4 Summary
Chapter 11 Domination in Planar Graphs
11.1 Introduction
11.2 Domination in Planar Graphs
11.2.1 Domination in Planar Triangulations
11.2.2 Domination in Outerplanar Graphs
11.2.3 Domination in Planar Graphs with Small Diameter
11.3 Total Domination in Planar Graphs
11.3.1 Total Domination in Outerplanar Graphs
11.3.2 Total Domination in Planar Graphs with Small Diameter
11.4 Independent Domination in Planar Graphs
Chapter 12 Domination Partitions
12.1 Introduction
12.2 Domatic Numbers
12.2.1 Domatically Full Graphs
12.2.2 Lower Bounds
12.2.3 Generalizations of the Domatic Number
Transitivity and Upper Domatic Number
Coalition Partitions
12.3 Idomatic Number
12.4 Total Domatic Number
12.4.1 Total Domatic Number in Graph Families
12.4.2 Total Domatic Number in Planar Graphs
12.5 Results of Zelinka on Domatic Numbers
12.6 Dominating Bipartitions of Graphs
12.6.1 Dominating and Total Dominating Set Partition
12.6.2 Total Dominating Set and Independent Dominating Set Partition
12.6.3 Partitions into Two Total Dominating Sets
Chapter 13 Domination Critical and Stable Graphs
13.1 Introduction
13.2 The Six Graph Families
13.2.1 CVR, CER, and CEA
13.2.2 UVR, UER, and UEA
13.2.3 Relationships Among the Families
13.3 Domination Vertex-Critical Graphs (CVR)
13.3.1 Vertex-Critical Graphs
13.3.2 3-Vertex-Critical Graphs
13.4 Domination Edge-Critical Graphs (CEA)
13.4.1 Properties of k-Edge-Critical Graphs
13.4.2 3-Edge-Critical Graphs
13.5 Total Domination Edge-Critical Graphs
13.5.1 k-t-Edge-Critical Graphs
13.5.2 3-t-Edge-Critical Graphs
Chapter 14 Upper Domination Parameters
14.1 Introduction
14.2 Upper Bounds
14.2.1 Upper Bounds in Terms of Minimum Degree
14.2.2 Upper Bounds in Regular Graphs
14.2.3 Upper Bounds in Claw-free Graphs
14.3 Upper Domination Number
14.4 Independence Number
Chapter 15 Relating the Core Parameters
15.1 Introduction
15.2 Well-covered andWell-dominated Graphs
15.2.1 Well-covered Graphs
15.2.2 Well-dominated Graphs
15.2.3 Well-total Dominated Graphs
15.3 Domination Versus Independent Domination
15.3.1 (gamma, i)-graphs
15.3.2 Domination Perfect Graphs
15.3.3 Regular Graphs
15.4 Domination Versus Total Domination
15.4.1 Regular Graphs
15.4.2 Claw-free Graphs
15.5 Upper Domination Versus Independence
15.6 Upper Domination Versus Upper Total Domination
15.6.1 Regular Graphs
15.7 Independence Versus Total Domination
15.7.1 Independent Domination Versus Total Domination
15.7.2 Independence Versus Total Domination
15.8 Summary
Chapter 16 Nordhaus-Gaddum Bounds
16.1 Introduction
16.2 Domination Number
16.2.1 Minimum Degree One
16.2.2 Minimum Degree Two
16.2.3 Minimum Degree Three
16.2.4 Minimum Degree Four
16.2.5 Minimum Degree Five
16.2.6 Minimum Degree Six
16.2.7 Summary of Bounds with Specified Minimum Degree
16.2.8 Multiple Factors
16.2.9 Relative Complement
16.3 Total Domination Number
16.4 Independent Domination Number
16.5 Upper Domination Parameters
16.5.1 Upper Domination and Independence Numbers
16.5.2 Upper Total Domination Number
16.6 Domatic Numbers of G and Ḡ
Chapter 17 Domination in Grids and Hypercubes
17.1 Introduction
17.2 Domination in Grids
17.2.1 Domination Numbers of Grids
17.2.2 Independent Domination Numbers of Grids
17.2.3 Total Domination Numbers of Grids
17.3 Domination in Hypercubes
Chapter 18 Domination and Vizing’s Conjecture
18.1 Introduction
18.2 Vizing’s Conjecture for the Domination Number
18.2.1 A Framework
18.2.2 Key Preliminary Lemmas
18.2.3 Classical Results Related to Vizing’s Conjecture
18.3 Total Domination Number
18.4 Independent Domination Number
18.5 Independence Number
18.6 Upper Domination Number
18.7 Upper Total Domination Number
Epilogue
Appendix A Glossary
A.1 Introduction
A.2 Basic Graph Theory Definitions
A.2.1 Basic Numbers
A.2.2 Common Types of Graphs
A.2.3 Graph Constructions
A.3 Graph Parameters
A.3.1 Connectivity and Subgraph Numbers
A.3.2 Distance Numbers
A.3.3 Covering, Packing, Independence, and Matching Numbers
A.3.4 Core Domination Numbers
A.3.5 Domatic Partitions
A.3.6 Perfect and Efficient Dominating Sets
A.3.7 Enclaveless Sets
A.3.8 Grid Graphs
A.4 Hypergraph Terminology and Concepts
Appendix B Books Containing Information on Domination in Graphs
Appendix C Surveys Containing Information on Domination in Graphs
Bibliography
Index
Symbol index
Subject index
Author index
