Narrow Results

The power graph of a group G is a simple graph whose vertex-set is G and two vertices x and y in G are adjacent if and only if one of them is a power of the other. The subgraph of is obtained by deleting the vertex 1 (the identity element of G). In this paper, we first investigate some properties of the power graph and its subgraph . We next provide necessary and sufficient conditions for a power graph to be a strongly regular graph, a bipartite graph or a planar graph. Finally, we obtain some infinite families of finite groups G for which the power graph contains some cut-edges.

Let $R$ be a commutative ring with identity, and let $Z(R)$ be the set of zero-divisors of $R$. The annihilator graph of $R$ is defined as the graph AG$(R)$ with the vertex set $Z{(R)}^{\ast }=Z(R)\backslash \{0\}$, and two distinct vertices $x$ and $y$ are adjacent if and only if ann${}_R(xy)\ne {\mathrm{\text{ann}}}_R(x)\cup {\mathrm{\text{ann}}}_R(y)$. In this paper, we study annihilator graphs of rings with equal clique number and chromatic number. For some classes of rings, we give an explicit formula for the clique number of annihilator graphs. Among other results, bipartite annihilator graphs of rings are characterized. Furthermore, some results on annihilator graphs with finite clique number are given.

We characterize all connected graphs with exactly three distinct normalized Laplacian eigenvalues among which one is equal to 1, and determine all connected bipartite graphs with at least one vertex of degree 1 having exactly four distinct normalized Laplacian eigenvalues. In addition, we find all unicyclic graphs with three or four distinct normalized Laplacian eigenvalues.

To assess the physico-chemical characteristics of protein-protein interactions, protein sequences and overall structural folds have been analyzed previously. To highlight this, discovery and examination of amino acid patterns at the binding sites defined by structural proximity in 3-dimensional (3D) space are essential. In this paper, we investigate the interacting preferences of 3D pattern pairs discovered separately in transient and obligate protein complexes. These 3D pattern pairs are not necessarily sequence-consecutive, but each residue in two groups of amino acids from two proteins in a complex is within certain Å threshold to most residues in the other group. We develop an algorithm called AA-pairs by which every pair of interacting proteins is represented as a bipartite graph, and it discovers all maximal quasi-bicliques from every bipartite graph to form our 3D pattern pairs. From 112 and 2533 highly conserved 3D pattern pairs discovered in the transient and obligate complexes respectively, we observe that Ala and Leu is the highest occuring amino acid in interacting 3D patterns of transient (20.91%) and obligate (33.82%) complexes respectively. From the study on the dipeptide composition on each side of interacting 3D pattern pairs, dipeptides Ala-Ala and Ala-Leu are popular in 3D patterns of both transient and obligate complexes. The interactions between amino acids with large hydrophobicity difference are present more in the transient than in the obligate complexes. On contrary, in obligate complexes, interactions between hydrophobic residues account for the top 5 most occuring amino acid pairings.

We describe here a technique of decomposition of bipartite graphs which seems to be as interesting within this context as the well known modular and split techniques for the decomposition of general graphs. In particular, we characterize by forbidden subgraphs the family of bipartite graphs which are totally decomposable (i.e. reducible to single vertices) with respect to our decomposition. This family contains previously known families of graphs such as bicographs and P₆-free bipartite graphs. As an application we provide polynomial solutions of optimization problems, some of them being NP-complete for general bipartite graphs.

We have recently shown that one can obtain the numbers and sizes of modules of a software system from the eigenvectors of its modularity matrix symmetrized and weighted by an affinity matrix. However such a weighting still demands a suitable definition of an affinity. This paper offers an alternative way to obtain the same results by means of the eigenvectors of a Laplacian matrix, directly obtained from the modularity matrix without the need of weighting. These two formalizations stand in a mutual isomorphism. We call it bipartite isomorphism since it is most straightforwardly shown by deriving the Laplacian from the modularity matrix and vice versa through the intermediate bipartite graph between two separate sets: the structors’ and the functionals’ sets. This isomorphism is also demonstrated through the equation defining the Laplacian in terms of the modularity matrix, or by the direct mapping of the respective matrices’ eigenvectors. Both matrices and the bipartite graph reflect one central idea: modules are connected components with high cohesion. The Laplacian matrix technique, of which the Fiedler vector is of central importance, is illustrated by case studies. An important claim of this paper is that, independently of the modularity matrix- and Laplacian matrix-specific properties, behind these two alternative matrices there is just one unified algebraic theory of software composition — the Linear Software Models — here concerning the application of the matrices’ eigenvectors to software modularity.

Let $X$ be a finite simple graph. The $2$-distance graph $D_2(X)$ of $X$ is the graph with the same vertex set as $X$ and two vertices are adjacent if and only if their distance in $X$ is exactly $2$. A graph $G$ is a $2$-distance graph if there exists a graph $X$ such that $D_2(X)\cong G$. In this paper, we give three characterizations of $2$-distance graphs, and find all graphs $X$ such that $D_2(X)\cong k{P}_2$ or $K_m\cup K_n$, where $k\ge 2$ is an integer, $P_2$ is the path of order $2$, and $K_m$ is the complete graph of order $m\ge 1$.

Let G be a connected graph. A set of vertices $\text{S }\subseteq \text{ V (G)}$ is called subverted from G if each of the vertices in S and the neighbor of S in G are deleted from G. By G/S we denote the survival subgraph that remains after S is subverted from G. A vertex set S is called a cut-strategy of G if G/S is disconnected, a clique, or ø. The vertex-neighbor-scattering number of G is defined by $\text{VNS(G) = }\underset{\text{S}\subseteq \text{V(G)}}{\text{max}}\text{{}\omega \text{(G/S)}\text{-}\mathrm{|S|}\text{}}$, where S is any cut-strategy of G, and ø(G/S) is the number of components of G/S. It is known that this parameter can be used to measure the vulnerability of spy networks and the computing problem of the parameter is NP-complete. In this paper, we discuss the vertex-neighbor-scattering number of bipartite graphs. The NP-completeness of the computing problem of this parameter is proven, and some upper and lower bounds of the parameter are also given.

In this paper, we study the signed $k$-domination and its total version in graphs. By a simple uniform approach we give some new upper and lower bounds on these two parameters of a graph in terms of several different graph parameters. In this way, we can improve and generalize some results in literature. Moreover, we make use of the well-known theorem of Turán [On an extremal problem in graph theory, Math. Fiz. Lapok48 (1941) 436–452] to bound the signed total $k$-domination number, ${\gamma }_{kS}^t(G)$, of a $K_{r+1}$-free graph $G$ for $r\ge 2$.