Search

This paper was written as a bachelor thesis in mathematics. We study adjacency matrices and their eigenvalues to investigate what properties of the corresponding graphs can be determined by those eigenvalues, the spectrum of the graph. The question of which graphs are uniquely determined by their spectra is also covered. Later on we study some methods of finding examples of graphs with shared spectra, also referred to as cospectral graphs.

Glavna svrha ovog rada je pokazati na koji način su povezana područja linearne algebre i teorije grafova te kako njihovu vezu možemo iskoristiti za rješavanje problema u stvarnom životu. U prvom poglavlju navodimo definicije, teoreme i rezultate iz linearne algebre i teorije grafova koji su nužni za shvaćanje glavnog dijela rada. Drugo, treće i četvrto poglavlje bavi se proučavanjem matrice susjedstva, matrice incidencije i Laplaceove matrice. Definiramo svaku od navedenih matrica, na stvarnim primjerima prikazujemo načine njihovog određivanja te prezentiramo njihove primjene u proučavanju pripadnih grafova. U petom i šestom poglavlju promatramo matricu udaljenosti stabla i matricu otpora. Definiramo navedene matrice i proučavamo njihova svojstva i primjene. Poseban naglasak je dan na rezultate vezane uz njihove svojstvene vrijednosti, determinante i povezanosti s Laplaceovom matricom. The main purpose of this thesis is to show the connections between linear algebra and graph theory and their applications to solving real life problems. In the first chapter we give basic definitions, theorems and results from linear algebra and graph theory which are vital for further understanding of the thesis. In chapters two, three and four we are focused on adjacency and incidence matrices along with the Laplacian matrix. We define each of these matrices, we show how to determine them by using real life examples and we present their applications to the study of the underlying graphs. In the last two chapters, chapters five and six, we examine the distance matrix of a tree and the resistance matrix. We introduce the aforementioned matrices and study their properties and applications. Special emphasis is given to the results concerning their eigenvalues, determinants and connections with the Laplacian matrix.

Two adjacent or non-adjacent vertices of a graph G are said to be identified, if they are combined to form one vertex whose neighbor is the union of their neighborhoods (ignoring any loops or multiple edges formed). The nullity of a graph G, denoted by η(G), is the multiplicity of the eigenvalue zero in its spectrum. A graph is a nullity critical if identifying any pair of vertices decreases or increases the nullity. On the other hand, a graph is a nullity- stable if identifying any pair of distinct vertices leaves the nullity unchanged. It is proved that in general, identifying any pair of distinct vertices cannot increase or decrease the nullity by at most 2. Also, nut graphs are constructed from old ones with smaller order and larger maximum degree. Our main tools to obtain such results are the interlacing theorem, the end vertex Lemma, the assignment of appropriate weights to the vertices which are going to be identified in a high zero sum weighting of the graph. The distance between vertices with the same weight plays an important role in the study of the change in the nullity on vertex identification in a graph.

Maximal Clique Enumeration (MCE) is a fundamental and challenging problem in graph theory and various network applications. Numerous algorithms have been proposed in the past decades, however, only a few of them focus on improving the practical efficiency in large graphs. To this end, we propose an efficient algorithm called FACEN based on the Bron–Kerbosch framework. To optimize the memory and time consumption, we apply a hybrid data structure with adjacency list and partial adjacency matrix, and introduce a dynamic pivot selection rule based on the degeneracy order. FACEN is evaluated on a total of 64 benchmark instances from various sources. Computational results indicate that the proposed algorithm is highly competitive with the current leading MCE methods. In particular, our algorithm is able to enumerate all maximal cliques on the tested real-world social networks with millions of vertices and edges. For very large graphs, we provide an additional experiment for solving the MCE variant with lower bound, and investigate the benefits of FACEN.

It is well known that spectral Tur\'{a}n type problem is one of the most classical {problems} in graph theory. In this paper, we consider the spectral Tur\'{a}n type problem. Let $G$ be a graph and let $\mathcal{G}$ be a set of graphs, we say $G$ is \textit{$\mathcal{G}$-free} if $G$ does not contain any element of $\mathcal{G}$ as a subgraph. Denote by $\lambda_1$ and $\lambda_2$ the largest and the second largest eigenvalues of the adjacency matrix $A(G)$ of $G,$ respectively. In this paper we focus on the characterization of graphs without short odd cycles according to the adjacency eigenvalues of the graphs. Firstly, an upper bound on $\lambda_1^{2k}+\lambda_2^{2k}$ of $n$-vertex $\{C_3,C_5,\ldots,C_{2k+1}\}$-free graphs is established, where $k$ is a positive integer. All the corresponding extremal graphs are identified. Secondly, a sufficient condition for non-bipartite graphs containing an odd cycle of length at most $2k+1$ in terms of its spectral radius is given. At last, we characterize the unique graph having the maximum spectral radius among the set of $n$-vertex non-bipartite graphs with odd girth at least $2k+3,$ which solves an open problem proposed by Lin, Ning and Wu [Eigenvalues and triangles in graphs, Combin. Probab. Comput. 30 (2) (2021) 258-270]., Comment: 15 pages. It is accepted by Discrete Mathematics

Biological organisms can vastly change their ecological functionality due to changes in body size and diet across their life. Consequently, it has been increasingly recognized that to attain sufficient biological realism, food webs may need to include life-history structures. The objective of the work is to study theoretically whether and how the inclusion of life-history structures affects the food web topology. Topological research was done by applying network theory metrics for three different food web types with two different sizes that were generated by using the niche-model. The dynamical modeling was performed by using an allometric trophic network modeling approach. The different types included food webs with and without the life-history structure for top predators (three fish species). Each of the generated random food webs analyzed reached dynamical equilibrium conditions with respect to the biomass densities of the species prior to the network analysis. Our results suggest that food web topologies are not largely affected by the inclusion of age- or stage-structure. In addition to the topological study, the relationship between the metrics used in this work was investigated by using Pearson correlation. Results suggested that only a few pairs of metrics had a strong positive correlation and most of the correlations did not change with food web size or type. peerReviewed

As part of studies that employ health electronic records databases, this paper advocates the employment of graph theory for investigating drug-switching behaviors. Unlike the shared approach in this field (comparing groups that have switched with control groups), network theory can provide information about actual switching behavior patterns. After a brief and simple introduction to fundamental concepts of network theory, here we present (i) a Python script to obtain an adjacency matrix from a records database and (ii) an illustrative example of the application of network theory basic concepts to investigate drug-switching behaviors. Further potentialities of network theory (weighted matrices and the use of clustering algorithms), along with the generalization of these methods to other kinds of switching behaviors beyond drug switching, are discussed.