Criticality of the lower domination parameters of graphs

[摘要] In this thesis we focus on the lower domination parameters of a graph G, denoted ¼(G), for¼ 2 {i, ir, °}. For each of these parameters, we are interested in characterizing the structure ofgraphs that are critical when faced with small changes such as vertex-removal, edge-addition andedge-removal. While criticality with respect to independence and domination have been welldocumented in the literature, many open questions still remain with regards to irredundance.In this thesis we answer some of these questions.First we describe the relationship between transitivity and criticality. This knowledge we thenuse to determine under which conditions certain classes of graphs are critical. Each of thechosen classes of graphs will provide specific examples of different types of criticality. We alsoformulate necessary conditions for graphs to be ir-critical and ir-edge-critical.

[发布机构] Stellenbosch University