Domination and so-energy in graphs

In this thesis, the concept of domination in graphs is examined in depth within the scope of graph theory, which is one of the fundamental areas of discrete mathematics. Graph theory is a mathematical discipline that models and analyzes the relationships between systems based on structures consisting of vertices (nodes) and edges connecting them. Graphs are considered powerful tools for understanding the structural properties of complex systems and for performing analyses on such systems. In this respect, graph structures are widely used in numerous fields such as social networks, communication and transportation systems, biological interaction networks, computer networks, and logistics planning. A significant part of the research conducted on graphs involves domination theory, which focuses on identifying subsets of vertices that can dominate or control the entire graph. Dominating sets are not only of theoretical interest but are also widely applied in practice. In particular, the concept of domination is effectively utilized in applications such as efficient resource allocation, communication network control, sensor placement problems, and bioinformatics analyses. The historical development of the domination concept reveals that it originates from the classical chess-based Five Queens Problem. In this problem, the goal is to place the minimum number of queens on a chessboard such that all squares are under threat. This idea has served as a foundational approach to domination problems in graphs. Over time, the concept has been expanded with the introduction of subtopics such as independent dominating sets, total domination, and connected domination. vii One of the fundamental problems related to domination is determining the size of the smallest dominating set in a graph, referred to as the domination number. This value is a key indicator of the efficiency of coverage in a graph. However, the complexity of this problem varies significantly depending on the type of graph. While the domination number can be computed efficiently in some specific graph classes (e.g., trees, cycles), it is generally NP-hard in arbitrary graphs, requiring high computational effort for exact solutions. Accordingly, the main objective of this thesis is to examine domination-related concepts in graphs from both theoretical and applied perspectives, thereby contributing to the existing literature and offering a framework for potential applications. Within this scope, the second chapter of the thesis introduces the basic concepts and definitions of graph theory. The third chapter presents various types of domination, along with related theorems, definitions, and bounds. The fourth and final chapter focuses on a graph invariant associated with dominating sets, known as soenergy, and includes soenergy computations on various graphs. Additionally, the study evaluates domination problems within the framework of computational complexity theory, emphasizing the challenges encountered in solving these problems and discussing approximation and parameterized algorithms developed as potential solutions. The findings of this research strengthen the theoretical foundations of domination in graph theory and provide a basis for future applications in diverse domains. In this respect, the study offers a meaningful contribution both in terms of mathematical theory and practical implementation in various scientific and engineering problems. Keywords: Graph theory, dominating set, domination number, NP-hardness, soenergy