Fuzzy graphs are designed to represent structures of relationships between objects where the existence of a concrete object and relationship between two objects are matters of degree. Most wide spread T-operators, min and max, have been used to introduce the structure of fuzzy graphs since their inception in literature and very little effort is done to make use of new operators. In this dissertation, we stress that the min and max operators are not the only candidates for the generalization of the classical graphs to fuzzy graphs and demonstrate the use of a particular Toperator, namely the Dombi operator in the area of fuzzy graph theory. The main objective of this dissertation is to introduce different concepts of graphs under generalized fuzzy circumstances and provide their pertinent applications in multi-attribute decision making. To obtain the desired goal, a new generalization of fuzzy graphs, called Pythagorean fuzzy graphs is proposed. Certain novel concepts, including the energy and Laplacian energy of Pythagorean fuzzy graphs are introduced. In particular, decision-making problems concerning the design of a satellite communication system and the evaluation of the schemes of reservoir operation are solved to illustrate the applicability and effectiveness of our proposed concepts. A series of operational laws of single-valued neutrosophic graphs is developed and their desirable properties are investigated in detail. A new decision making approach is developed in the context of graph theory to deal with the multi-attribute decision making problems in hesitant fuzzy circumstances. Further, the developed approach is generalized to make it suitable for processing interval-valued hesitant fuzzy and hesitant triangular fuzzy information. The numerical examples concerning the energy project selection and software evaluation are utilized to show the detailed implementation procedure and reliability of our method in solving multi-attribute decision making problems. Furthermore, the results related to graphs and hypergraphs are reformulated in the context of interval-valued intuitionistic fuzzy sets. Meanwhile, the theory of intervalvalued intuitionistic fuzzy transversals associated with interval-valued intuitionistic fuzzy hypergraphs is introduced.