30 out 2020
10:00 Master's Defense Fully distance
Theme
Dominant Sets in Cubic Graphs
Student
Alessandra Aparecida Pereira
Advisor / Teacher
Christiane Neme Campos
Brief summary
A set S ⊆ V (G) is a dominant set if every vertex of G is an element of S or is adjacent to an element of S. An independent dominant set of G is both a dominant set and an independent set in G. We call the cardinality of a smaller dominant set of G as the domination number. This parameter is denoted by γ (G). In this paper, we present a brief history of the problems of dominant sets and some of their variations. Of these variations, in particular, we address the number of G-independent dominance, denoted by i (G) and defined as the cardinality of a smaller dominant set independent of G. Determine γ (G) and i (G) for an arbitrary graph G are NP-difficult problems, even when restricted to cubic graphs. In fact, there is much interest in the study of cubic graphs in the context of domination. In particular, in 1996, B. Reed conjectured that connected cubic graphs G have γ (G) ≤ ⌈n / 3⌉. Although A. Kostochka and B. Stodolsky have shown that this conjecture is false in the general case, much research has been done in search of families of cubic graphs that verify or improve the Reed limiter. In this text, we determine the number of domination and the number of independent domination of some families of cubic graphs. In addition, another point addressed in this text is the relationship between γ (G) and i (G). As every independent dominant set is a dominant set, it follows that γ (G) ≤ i (G). Deciding whether γ (G) = i (G) is also an NP-complete problem. In fact, even when restricted to cubic and connected graphs, the difference i (G) - γ (G) can be arbitrarily large. All these considerations motivate both the study of cubic graphs with a domination number limited by the value of Reed's conjecture, as well as the determination of the number of independent domination of these graphs, to assess how far these two parameters are. In this work, this analysis is done for the classes considered.
Examination Board
Headlines:
| Christiane Neme Campos | IC / UNICAMP |
| José Coelho de Pina Junior | IME / USP |
| Orlando Lee | IC / UNICAMP |
Substitutes:
| Guilherme Pimentel Telles | IC / UNICAMP |
| Carmen Cecilia Centeno | ECEC / PUC Goiás |