abstract: This thesis addresses large graphs in advanced applications. We study three aspects of graphs: graph indices, graph models, and graph robustness.
Measures and indices are used to represent structural properties of networks and graphs. In chemical graph theory, graph indices, called chemical descriptors help us to predict the properties or activities of chemical compounds. This method reduces the expenses involved in finding appropriate medicine or chemical compound with the desired properties. In this context the thesis focuses on the Wiener index, and the problem of specifying a graph family for which the Wiener index equals the Wiener index of its line graph. We further study centrality indices that are used to determine the relative importance of a given vertex or an edge in the complex graph. In this respect, we introduce two new centrality indices: degree-scaled betweenness centrality and degree-weighted betweenness centrality. We prove the extremal values of these indices and determine the graph structures in which the extremal values are attained.
In the study of real-world complex networks, graphs as network models help us to understand interactions within networks. In the thesis we introduce a new social network model, called the interaction-based model, which is based on well-known sociological principles. In particular, this model is based on balance theory in combination with pheromone deposition and evaporation found in the social behavior of ants. The interactions between individuals are modeled by pheromone, which appear according to the balance theory and change the connection strength between individuals. Therefore, the human social systems are living structures where many simultaneous interactions occur between individuals and each present interaction influences future interactions. In the interaction-based model, each interaction between two individuals influences future interactions similarly to how pheromone trails influence the ant’s future decision of its path. We calculate and analyze characteristics of different network models and real-world network to evaluate and validate the model.
The last aspect concerns the resilience of the network to the removal of edges or the robustness of network. In this context the thesis focuses on the hypercubes as one of the widely studied graph architectures due to its elegant properties. These hypercubes have also been used to design real parallel networks. More specifically, we study the maximal number of mutually-independent Hamiltonian paths with prescribed end-vertices. The obtained result is used to prove the upper bound of the number of mutually-independent s-starting Hamiltonian cycles in the hypercube with faulty edges.
