Resumen de Total protection in graphs

Abel Cabrera Martinez

• A significant part of the growth that discrete mathematics has experienced in recent years has consisted of a substantial development in graph theory, which is the area where our research is concentrated. Apart from the influence of graph theory to the development of discrete mathematics, the relevance and generality of this research area is well supported, given that often provides the models and techniques to dial with problems arising from diverse fields as computer science, telecommunications, logistics, chemistry, biology, medicine, social sciences, among others.

  Domination theory is a well-established topic in graph theory, as well as one of the most active research area. Domination was first defined as a graph-theoretical concept in 1958. This area experienced rapid growth resulting in over 1200 papers published by the late 1990s. The explosive growth has continued and today more than 4500 papers have been published on domination in graphs. The increasing interest in this area is partly explained by the diversity of applications to real-world problems, such as facility location problems, computer and social networks, monitoring communication, coding theory, algorithm design, among others.The very dynamic growth of this topic makes incalculable the great number of open problems and possible lines of work.

  The notion of protection of graphs is closely related to the idea of domination. Recently, many authors have considered the following approach to the problem of protecting a graph: suppose that one or more entities are stationed at some of the vertices of a simple graph and that an entity at a vertex can deal with a problem at any vertex in its closed neighbourhood. In general, an entity could consist of a robot, an observer, a legion, a guard, and so on. Informally, we say that a graph is protected under a given placement of entities if there exists at least one entity available to handle a problem at any vertex.

  Various strategies (or rules for entities placements) have been considered, under each of which the graph is deemed protected. These strategies for the protection of graphs are framed within the theory of domination in graphs, or in the theory of secure domination in graphs.

  In this thesis, we introduce the study of (secure) w-domination in graphs, which is a unified approach to the idea of protection of graphs, that encompasses known variants of (secure) domination in graphs and introduces new ones. As we can expect, the minimum number of entities required for protection under each strategy is of interest. In general, we obtain closed formulas or tight bounds on the studied parameters.

  This thesis focuses on basic research in discrete mathematics. In this sense, the main methodological approach is that of theoretical research. Our main tools come from the areas of combinatorics, graph theory, algorithmics and complexity theory.

  The principal contributions of this thesis are summarized in ten papers published in JCR-indexed journals. These papers were presented in separated chapters.

  In Chapter 1 we introduced the study of w-domination in graphs, and provided general results on the w-domination number.

  The next three chapters are dedicated to the study of total protection strategies, associated to the w-domination in graphs. The first one, deals with the problem of finding the total domination number for the case of rooted product graphs. Chapters 3 and 4 are devoted to total Italian domination in graphs. In the first one, we introduced this parameter and studied its combinatorial and computational properties. The second one deals with the case of lexicographic product graphs.

  In Chapter 5 we introduced the study of secure w-domination in graphs, and we provided general results on the secure wdomination number.

  The next four chapters are devoted to the study of two total protection strategies, associated to secure w-domination in graphs. In Chapter 6 we introduced the study of the total weak Roman domination number of a graph. In Chapter 7 we obtained new relationships between the secure total domination number and other graph parameters. In Chapter 8 we considered the secure total domination number for the particular case of rooted product graphs. Finally, Chapter 9 deals with the case of lexicographic product graphs, where we showed that the secure total domination number and the total weak Roman domination number coincide for this class of graphs.

  Finally, in Chapter 10 we showed how the secure (total) domination number and the (total) weak Roman domination number of lexicographic product graphs are related to the (secure) w-domination number of the first graph factor involved in this product.