Theory And Algorithm Of Several Kinds Of Domination Parameters In Graphs

Within the last more than thirty years, concurrent with the growth of computer science and communication networks, graph theory has seen explosive growth. Perhaps the fastest-growing area within graph theory is the study of domination in graphs. As an important research field in graph theory, domination theory has many and varied applications in related fields, such as computer science, communication networks, coding theory, operations search, and social sciences. Now, most researchers in domination concentrate their attention on the following four aspects: (1) Determining the bounds on several domination parameters and investigating the relationships between domination parameters and other graphical parameters, such as chromatic number; (2) Studying the algorithmic complexity of domination-related parameters and designing algorithm of domination-related parameters; (3) Researching the dominating function and related parameters; (4) Discussing applications of domination theory in other fields.In this paper, we pay our attention mainly on the following five parts:1. We determine the upper bounds on power domination number for general graphs and claw-free cubic graphs, and characterize the extremal graphs attaining the upper bounds; Furthermore, we discuss the bounds on power domination number for outerplanar graphs and general planar graphs.2. We study two kinds of new dominating functions: minus edge dominating function and minus star dominating function; Then, we present some bounds on them and characterize the extremal graphs of even order attaining the upper bound on minus edge domination number; Furthermore, we investigate the relationships between them and other related parameters.3. We characterize the extremal graphs attaining the upper bound on 2-domination number for general connected graphs.