TY - CHAP
T1 - General Bounds
AU - Haynes, Teresa W.
AU - Hedetniemi, Stephen T.
AU - Henning, Michael A.
N1 - Publisher Copyright:
© Springer Nature Switzerland AG 2023.
PY - 2023
Y1 - 2023
N2 - As we have seen in Chapter 3, the decision problems associated with computing the domination, total domination, and independent domination numbers of arbitrary graphs are all NP-complete. Given the difficulty of determining the exact values of these domination numbers, much of the research involves the determination of tight lower and upper bounds for these numbers. In this chapter, we present some of the more basic bounds on the domination, total domination, and independent domination numbers of graphs. Additional bounds on these parameters will be given throughout the text, particularly in Chapter 6 in terms of minimum degree and Chapter 8 in terms of size.
AB - As we have seen in Chapter 3, the decision problems associated with computing the domination, total domination, and independent domination numbers of arbitrary graphs are all NP-complete. Given the difficulty of determining the exact values of these domination numbers, much of the research involves the determination of tight lower and upper bounds for these numbers. In this chapter, we present some of the more basic bounds on the domination, total domination, and independent domination numbers of graphs. Additional bounds on these parameters will be given throughout the text, particularly in Chapter 6 in terms of minimum degree and Chapter 8 in terms of size.
UR - http://www.scopus.com/inward/record.url?scp=85159105289&partnerID=8YFLogxK
U2 - 10.1007/978-3-031-09496-5_4
DO - 10.1007/978-3-031-09496-5_4
M3 - Chapter
AN - SCOPUS:85159105289
T3 - Springer Monographs in Mathematics
SP - 73
EP - 98
BT - Springer Monographs in Mathematics
PB - Springer Science and Business Media Deutschland GmbH
ER -