TY - CHAP
T1 - Probabilistic Bounds and Domination in Random Graphs
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 - In Chapter 6, we presented upper bounds on the domination number of a graph in terms of its order n and minimum degree δ. For small δ, the best known bounds to date are summarized in Table 6.5 in Chapter 6. Recall that for δ ϵ [3], the bounds given in the table are tight, while for all values of δ ≥ 4, no tight bound on the domination number is yet known. When δ is sufficiently large, optimal bounds on the domination number can be found using the Probabilistic Method. We present several such probabilistic bounds, including one for the total domination number, in this chapter.
AB - In Chapter 6, we presented upper bounds on the domination number of a graph in terms of its order n and minimum degree δ. For small δ, the best known bounds to date are summarized in Table 6.5 in Chapter 6. Recall that for δ ϵ [3], the bounds given in the table are tight, while for all values of δ ≥ 4, no tight bound on the domination number is yet known. When δ is sufficiently large, optimal bounds on the domination number can be found using the Probabilistic Method. We present several such probabilistic bounds, including one for the total domination number, in this chapter.
UR - http://www.scopus.com/inward/record.url?scp=85159081274&partnerID=8YFLogxK
U2 - 10.1007/978-3-031-09496-5_7
DO - 10.1007/978-3-031-09496-5_7
M3 - Chapter
AN - SCOPUS:85159081274
T3 - Springer Monographs in Mathematics
SP - 209
EP - 226
BT - Springer Monographs in Mathematics
PB - Springer Science and Business Media Deutschland GmbH
ER -