Domination in Graphs

Nawarat Ananchuen (), Watcharaphong Ananchuen and Michael D. Plummer
Additional contact information
Nawarat Ananchuen: Silpakorn University, Department of Mathematics, Faculty of Science

Chapter Chapter 4 in Structural Analysis of Complex Networks, 2011, pp 73-104 from Springer

Abstract: Abstract A set of vertices S in a graph G dominates G if every vertex in G is either in S or adjacent to a vertex in S. The size of any smallest dominating set is called the domination number of G. Two variants on this concept that have attracted recent interest are total domination and connected domination. A set of vertices S is a total dominating set if every vertex in the graph is adjacent to a vertex of S and S is a connected dominating set if it is dominating and, in addition, induces a connected subgraph. The size of any smallest total dominating set in G is called the total domination number of G and the size of a smallest connected dominating set is the connected domination number of G. These simple, yet wide-ranging, graph-theoretic concepts have a multitude of real-world applications. There are already in print several surveys of results on domination; therefore, in this chapter we adopt a slightly different approach. We begin by surveying results on bounding the three domination numbers. We then focus on criticality concepts for domination. The two types of criticality most widely studied to date are graphs for which the domination number decreases upon the addition of any missing edge and the graphs for which the domination number decreases upon the deletion of any vertex. Recently, there has been increased activity in the study of these critical concepts and we survey these new results, focusing especially upon matching in critical graphs.

Keywords: Domination; Total domination; Connected domination; Edge critical; Vertex critical; Matching (search for similar items in EconPapers)
Date: 2011
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-0-8176-4789-6_4

Ordering information: This item can be ordered from
http://www.springer.com/9780817647896

DOI: 10.1007/978-0-8176-4789-6_4

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().