Structures of Domination in Graphs

Preface
Contents
Glossary of Common Terms
1 Introduction
2 Basic Terminology
2.1 Basic Graph Theory Definitions
2.2 Common Types of Graphs
2.3 Graph Constructions
3 Graph Parameters
3.1 Connectivity and Subgraph Numbers
3.2 Distance Numbers
3.3 Covering, Packing, Independence, and Matching Numbers
3.4 Domination Numbers
References
Part I Related Parameters
Broadcast Domination in Graphs
1 Introduction
2 The Dual of Broadcast Domination
3 Broadcast Domination in Trees
4 Broadcast Domination in Graph Products
5 Irredundant Broadcasts
6 Independent Domination Broadcasts
7 k-Broadcast Domination
8 Limited Broadcast Domination
9 Algorithmic and Complexity Results
10 Concluding Comments
References
Alliances and Related Domination Parameters
1 Introduction
2 Preliminary Definitions and Background
2.1 Unfriendly Sets and Satisfactory Partitions
2.2 (σ, )-sets
2.3 Signed Domination
2.4 Minus Domination
2.5 Strong and Weak Dominating Sets
2.6 α-Dominating Sets
2.7 Communities
3 Alliances
4 Global Defensive Alliances
4.1 Bounds for General Graphs
4.2 Bounds for Trees
4.2.1 Upper Bounds
4.2.2 Lower Bounds
5 Related Parameters and Future Work
5.1 Cost Effective and Distribution Sets
5.1.1 Cost Effective Sets
5.1.2 Distribution Centers
5.1.3 Future Research
References
Fractional Domatic, Idomatic, and Total Domatic Numbersof a Graph
1 Introduction
2 The Fractional Domatic Number
3 The Fractional Idomatic Number
4 The Fractional Total Domatic Number
5 Fractional Definitions and Hypergraphs
6 More on Hypergraphs
7 Conclusion
References
Dominator and Total Dominator Colorings in Graphs
1 Introduction
2 Graph Theory Notation
3 Dominator Colorings
3.1 Bounds on the Dominator Chromatic Number
3.2 Special Classes of Graphs
3.2.1 Bipartite Graphs
3.2.2 Trees
3.2.3 Chordal Graphs and Split Graphs
3.2.4 Proper Interval Graphs and Block Graphs
3.2.5 P4-Free Graphs
3.2.6 Other Classes
3.3 Graph Products
3.4 Dominator Partition Number
3.5 Algorithmic and Complexity Results
4 Total Dominator Colorings
4.1 Bounds on the Total Dominator Chromatic Number
4.2 Special Classes of Graphs
4.2.1 Bipartite Graphs
4.2.2 Trees
4.2.3 Mycielskian of a Graph
4.2.4 Circulants
4.2.5 Central Graphs
4.3 Graph Products
4.4 Algorithmic and Complexity Results
5 Concluding Comments
References
Irredundance
1 Partition of V(G) Associated with an Irredundant Set
1.1 Private Neighbours
1.2 The Private Neighbour Cube and Generalised Irredundance
2 The Domination Chain
3 Equality of Parameters in the Domination Chain
3.1 Lower Irredundance Perfect Graphs
3.2 Upper Irredundance Perfect Graphs
3.3 (ir,IR)-Graphs
3.4 (ir,γ)-Graphs
3.5 (α,IR)- and (Γ,IR )-Graphs
4 Bounds Involving Other Graph Parameters
4.1 General Graphs
4.1.1 Bounds for ir
4.1.2 Bounds for coir and oir
4.1.3 Bounds for IR
4.1.4 Nordhaus-Gaddum-Type Results
4.1.5 Gallai-Type Results for ir and IR
4.2 Specific Graph Classes
4.2.1 Trees
4.2.2 Claw-Free Graphs
4.2.3 Other Graphs
5 Differences Between Parameters in the Domination Chain
5.1 Differences Between Lower Parameters
5.2 Differences Between Upper Parameters
5.3 Ratios of Lower Parameters
5.4 Ratios of Upper Parameters
6 Criticality and Stability
6.1 Criticality
6.1.1 Criticality of ir
6.1.2 Criticality of IR
6.2 Stability
7 Chessboards
7.1 Exact Values
7.2 Bounds
7.2.1 Bounds for the Queens Graph
7.2.2 Bounds for the Kings Graph
7.2.3 Bounds for Grids
8 Irredundant Ramsey Numbers
8.1 Exact Values
8.2 Bounds
9 Reconfiguration
10 Complexity
References
The Private Neighbor Concept
1 Introduction
2 Private Neighbors
3 Irredundant Sets
4 The Basic Private Neighbors and Corresponding Irredundance Numbers
5 Generalized Irredundance by Cockayne
6 Total Irredundance Numbers
7 The Covering Chain, a Dual of the Domination Chain
8 Domination in Terms of Perfection in Graphs
9 Partitions Involving Irredundant Sets
10 The Mystery of the Domination Chain: ??=≤ir(G)=≤γ(G)=≤i(G)=≤α(G)=≤Γ(G)=≤IR(G)=≤??
11 Broadcast Irredundance in Graphs
12 Roman Irredundance in Graphs
13 Fractional Irredundance
14 Open Problems Involving Irredundance
References
An Introduction to Game Domination in Graphs
1 Introduction
2 Domination-Type Games
2.1 The Domination Game
2.2 The Total Domination Game
2.3 The Independent Domination Game
3 Basic Properties
4 Paths and Cycles
5 Continuation and Total Continuation Principles
6 Upper Bounds and Conjectured Upper Bounds
6.1 Domination Game Bounds
6.2 Total Domination Game Bounds
6.3 Independent Domination Game Bounds
7 Trees
7.1 The Domination Game in Trees
7.2 The Total Domination Game in Trees
7.3 The Independent Domination Game in Trees
8 Computational Complexity
References
Domination and Spectral Graph Theory
1 Introduction
2 Adjacency Matrix
2.1 Domination and Spectral Radius
2.2 Domination and Energy
2.3 Other Results
3 Laplacian Matrix
3.1 Largest Eigenvalue
3.2 Second Smallest Eigenvalue
3.3 Disjoint Dominating Sets
3.4 Laplacian Distribution
3.5 A Spectral Nordhaus–Gaddum Result
4 Signless Laplacian Matrix
4.1 Bounds for the Index
4.2 Bounds for the Smallest Signless Laplacian Eigenvalue
4.3 k-Domination and Bounds for Q-Eigenvalues
5 Distance Matrices
6 Final Remarks and Open Problems
References
Varieties of Roman Domination
1 Introduction
2 Weak Roman Domination
2.1 Relationships with γR and γ
2.2 Nordhaus–Gaddum Type Bounds
2.3 Algorithmic and Complexity Results
3 Independent Roman Domination
3.1 Bounds on iR
3.2 Relationships Between iR and γR
3.3 Relationships Between iR and i
3.4 Algorithmic and Complexity Results
4 Roman k-Domination
4.1 Bounds on γkR and Relationships with γk
4.2 Relationships Between γkR and γR
4.3 k-Roman Graphs
4.4 Algorithmic and Complexity Results
5 Roman "4266308 2"5267309 -Domination
5.1 Bounds on γ"4266308 R2"5267309 and Relationships with γ, γ2, γr, and γR
5.2 Nordhaus–Gaddum Type Bounds
5.3 Algorithmic and Complexity Results
6 Double Roman Domination
6.1 Bounds on γdR and Relationships with γ, γR, γ"4266308 R2"5267309 , and γ2
6.2 Nordhaus–Gaddum Type Bounds
6.3 Algorithmic and Complexity Results
7 Total Roman Domination
7.1 Bounds and Relations with Some Domination Parameters
7.2 Algorithmic and Complexity Results
8 Perfect Roman Domination
8.1 Bounds
8.2 Algorithmic and Complexity Results
9 Strong Roman Domination
10 Edge Roman Domination
11 Open Problems
References
Part II Domination in Selected Graph Families
Domination and Total Domination in Hypergraphs
1 Introduction
2 Domination in Hypergraphs
2.1 Disjoint Dominating Sets
2.2 The Relationship Between Domination and Transversal
2.3 Upper Bounds on the Domination Number
2.4 Edge Size at Least Three
2.5 Edge Size at Least Four
2.6 Edge Size at Least Five
2.7 A Characterization of Hypergraphs Achieving Equality in Theorem 14
2.8 General Setting
2.9 Hypergraphs with Given Domination Number
2.9.1 The Case γ==1
2.9.2 The Case γ==2
2.9.3 The Case γ=≥3
2.10 Nordhaus–Gaddum-Type Results
2.11 Equality of Domination and Transversal Numbers
2.12 The Relationship Between Domination and Matching
3 Total Domination in Hypergraphs
4 Conjectures and Open Problems
References
Domination in Chessboards
1 Introduction
2 Historical Origins
3 Early Chessboard Domination
4 Queens
5 Bishops
6 Knights
7 Kings
8 Rooks
9 Other Varieties of Chessboard Domination Problems
References
Domination in Digraphs
1 Introduction
1.1 Basic Terminology and Notation
1.2 Domination and Independence
2 Background and History
2.1 Basis of the Second Kind
2.2 Kernels in Digraphs
3 Bounds on In, Out, and Twin Domination Numbers
3.1 (Out)-Domination
3.2 In-Domination
3.3 Domination and In-Domination
3.4 Twin Domination
3.5 Reverse Domination
4 Domination in Digraph Products
5 Domination in Oriented Graphs
5.1 Oriented Graphs
5.2 Tournaments
6 Total Domination in Digraphs
6.1 Total Domination: Version 1
6.2 Total Domination: Version 2
6.3 Total Domination: Version 3
6.4 Total Domination: Version 4
6.5 Fractional Domination in Digraphs
7 The Oriented Version of the Domination Game
8 Concluding Comments
References
Part III Algorithms and Complexity
Algorithms and Complexity of Signed, Minus, and MajorityDomination
1 Introduction to Y-Dominating Functions
1.1 Y=="4266308 0, 1"5267309 with f(N[v])=≥1
1.2 Y==[0, 1] with f(N[v])=≥1
1.3 Y=="4266308 −1, 1"5267309 with f(N[v])=≥1
1.4 Y=="4266308 −1, 0, 1"5267309 with f(N[v])=≥1
1.5 Y=="4266308 0, 1"5267309 with f(N(v))=≥1
1.6 Y==[0, 1] with f(N(v))=≥1
1.7 Y=="4266308 −1, 1"5267309 with f(N(v))=≥1
1.8 Y=="4266308 −1, 0, 1"5267309 with f(N(v))=≥1
1.9 Y=="4266308 −1, 1"5267309 with f(N[v])=≥1 for at least half of the vertices v=V
2 Signed Domination
3 Minus Domination
4 Signed and Minus Total Domination
4.1 Y=="4266308 −1, 1"5267309 with f(N(v))=≥1
4.2 Y=="4266308 −1, 0, 1"5267309 with f(N(v))=≥1
5 Majority Domination
6 Efficient Y-Domination
7 Signed Star Domination
8 Open Problems
References
Algorithms and Complexity of Power Domination in Graphs
1 Power Domination in Graphs
References
Self-Stabilizing Domination Algorithms
1 Introduction
2 Self-Stabilizing Framework
2.1 Program and Computation
2.2 Distance-k Knowledge
2.3 Anonymous Systems
2.4 Schedulers
2.5 Self-Stabilization
2.6 Running Times
2.7 Rationale for Self-Stabilizing Algorithms
3 Self-Stabilizing Maximal Independent Set Algorithms
3.1 Distributed Model Maximal Independent Set Algorithm
3.2 Synchronous Model Maximal Independent Set Algorithm
3.3 Other Self-Stabilizing Independent Set Algorithms
4 Self-Stabilizing Maximal Matching Algorithms
4.1 Central Model Maximal Matching Algorithm
4.2 Synchronous and Distributed Model Maximal Matching Algorithm
4.3 Other Self-Stabilizing Matching Algorithms
5 Self-Stabilizing Dominating Set Algorithms
5.1 Central Model Minimal Dominating Set Algorithm
5.2 Synchronous Model Minimal Dominating Set Algorithm
5.3 Distributed Model Minimal Dominating Set Algorithm
5.4 Minimal Total Dominating Set Algorithm
6 Other Self-Stabilizing Domination Algorithms
7 Avenues for Further Study
References
Algorithms and Complexity of Alliances in Graphs
1 Introduction
2 Algorithms and Complexity of Alliances in Graphs
2.1 Self-Stabilizing Alliance Algorithms
3 Open Problems
References