Narrow Results

In this paper, we propose a new algorithm that minimizes the worst expected growth of an epidemic by reducing the size of the largest connected component (LCC) of the underlying contact network. The proposed algorithm is applicable to any level of available resources and, despite the greedy approaches of most immunization strategies, selects nodes simultaneously. In each iteration, the proposed method partitions the LCC into two groups. These are the best candidates for communities in that component, and the available resources are sufficient to separate them. Using Laplacian spectral partitioning, the proposed method performs community detection inference with a time complexity that rivals that of the best previous methods. Experiments show that our method outperforms targeted immunization approaches in both real and synthetic networks.

This paper undertakes a social network analysis of two science fiction television series, Stargate and Star Trek. Television series convey stories in the form of character interaction, which can be represented as “character networks”. We connect each pair of characters that exchanged spoken dialogue in any given scene demarcated in the television series transcripts. These networks are then used to characterize the overall structure and topology of each series. We find that the character networks of both series have similar structure and topology to that found in previous work on mythological and fictional networks. The character networks exhibit the small-world effects but found no significant support for power-law. Since the progression of an episode depends to a large extent on the interaction between each of its characters, the underlying network structure tells us something about the complexity of that episode’s storyline. We assessed the complexity using techniques from spectral graph theory. We found that the episode networks are structured either as (1) closed networks, (2) those containing bottlenecks that connect otherwise disconnected clusters or (3) a mixture of both.

The generalized windmill graphs are good models for many real-world networks. In this paper, we obtain analytic expressions for the eigenvalues of the adjacency matrices and of the Laplacian matrices of the generalized windmill graphs. Using this information, we study some structural and dynamical properties of these graphs. To the end, we investigate the metro networks of four France cities and propose our suggestions for the planning of public transport networks.

In this paper, we present a growing complex network model, namely, the generalized corona network (GCN) which is built on a base network and a sequence of networks by using corona product of graphs. This construction generalizes several existing complex network models. We study the structural properties of the special classes of generalized corona networks and show that these networks have small diameter, the cumulative betweenness distribution follows a power-law distribution, the degree distribution decay exponentially, small average path length with the network order, high clustering coefficient and small-world behavior. Further, we obtain the spectra of the adjacency matrix and the signless Laplacian matrix of GCN when the constituting networks are regular. Also, we obtain the Laplacian spectra for all generalized corona networks. In addition, explicitly give eigenvector corresponding to the adjacency and Laplacian eigenvalues. Finally, we derive the spectral radius and the algebraic connectivity of GCN.

The commuting graph ${𝒞}(\mathrm{\Omega },G)$ of a finite group $G$ has vertex set as $\mathrm{\Omega }\subseteq G$, and any two distinct vertices $x,y$ are adjacent if $x$ and $y$ commute with each other. In this paper, we first study the perfect codes of ${𝒞}(\mathrm{\Omega },G)$. We then find the universal adjacency spectra of the join of two regular graphs, join of two regular graphs in which one graph is a union of two regular graphs, and generalized join of regular graphs in terms of adjacency spectra of the constituent graphs and an auxiliary matrix. As a consequence, we obtain the adjacency, Laplacian, signless Laplacian, and Seidel spectra of the above graph operations. As an application of the results obtained, we calculate the adjacency, Laplacian, signless Laplacian, and Seidel spectra of ${𝒞}(G,G)$ for $G\in \{{\mathrm{\text{D}}}_n,{\mathrm{\text{Dic}}}_n,{\mathrm{\text{SD}}}_n\}$, where ${\mathrm{\text{D}}}_n$ is the dihedral group, ${\mathrm{\text{Dic}}}_n$ is the dicyclic group and ${\mathrm{\text{SD}}}_n$ is the semidihedral group. Moreover, we provide the exact value of the spectral radius of the adjacency, Laplacian, signless Laplacian, and Seidel matrix of ${𝒞}(G,G)$ for $G\in \{{\mathrm{\text{D}}}_n,{\mathrm{\text{Dic}}}_n,{\mathrm{\text{SD}}}_n\}$. Some of the theorems published in [F. Ali and Y. Li, The connectivity and the spectral radius of commuting graphs on certain finite groups, Linear Multilinear Algebra 69 (2019) 1–14; T. Cheng, M. Dehmer, F. Emmert-Streib, Y. Li and W. Liu, Properties of commuting graphs over semidihedral groups, Symmetry 13(1) (2021) 103] can be deduced as corollaries from the theorems obtained in this paper.

The sequence and structure of a large body of proteins are becoming increasingly available. It is desirable to explore mathematical tools for efficient extraction of information from such sources. The principles of graph theory, which was earlier applied in fields such as electrical engineering and computer networks are now being adopted to investigate protein structure, folding, stability, function and dynamics. This review deals with a brief account of relevant graphs and graph theoretic concepts. The concepts of protein graph construction are discussed. The manner in which graphs are analyzed and parameters relevant to protein structure are extracted, are explained. The structural and biological information derived from protein structures using these methods is presented.