Search

The α-Hermitian adjacency matrix Hα of a mixed graph X has been recently introduced. It is a generalization of the adjacency matrix of unoriented graphs. In this paper, we consider a special case of the complex number α. This enables us to define an incidence matrix of mixed graphs. Consequently, we define a generalization of line graphs as well as a generalization of the signless Laplacian adjacency matrix of graphs. We then study the spectral properties of the gamma-signless Laplacian adjacency matrix of a mixed graph. Lastly, we characterize when the signless Laplacian adjacency matrix of a mixed graph is singular and give lower and upper bounds of number of arcs and digons in terms of largest and lowest eigenvalue of the signless Laplacian adjacency matrix.

Let G be a graph. An edge orientation of G is called smooth if the in-degree and the out-degree of every vertex differ by at most one. In this paper, we show that if G is a 2-edge-connected non-bipartite graph with δ ( G ) ≥ 3 , then G has a smooth primitive orientation. Among other results, using the spectral radius of digraphs, we show that if D 1 is a primitive regular orientation and D 2 is a non-regular orientation of a given graph, then for sufficiently large t , the number of closed walks of length t in D 1 is more than the number of closed walks of length t in D 2 . [ABSTRACT FROM AUTHOR]

In the paper, we introduce the signless Laplacian A B C -matrix Q ̃ (G) = D ¯ (G) + A ̃ (G) , where D ¯ (G) is the diagonal matrix of A B C -degrees and A ̃ (G) is the A B C -matrix of G. The eigenvalues of the matrix Q ̃ (G) are the signless Laplacian A B C -eigenvalues of G. We give some basic properties of the matrix Q ̃ (G) , which includes relating independence number and clique number with signless Laplacian A B C -eigenvalues. For bipartite graphs, we show that the signless Laplacian A B C -spectrum and the Laplacian A B C -spectrum are the same. We characterize the graphs with exactly two distinct signless Laplacian A B C -eigenvalues. Also, we consider the problem of the characterization of the graphs with exactly three distinct signless Laplacian A B C -eigenvalues and solve it for bipartite graphs and, in some cases, for non-bipartite graphs. We also introduce the concept of the trace norm of the matrix Q ̃ (G) − t r (Q ̃ (G)) n I , called the signless Laplacian A B C -energy of G. We obtain some upper and lower bounds for signless Laplacian A B C -energy and characterize the extremal graphs attaining it. Further, for graphs of order at most 6, we compare the signless Laplacian energy and the A B C -energy with the signless Laplacian A B C -energy and found that the latter behaves well, as there is a single pair of graphs with the same signless Laplacian A B C -energy unlike the 26 pairs of graphs with same signless Laplacian energy and eight pairs of graphs with the same A B C -energy. [ABSTRACT FROM AUTHOR]

Maximal biclique (also known as complete bipartite) subgraphs can model many applications in Web mining, business, and bioinformatics. Enumerating maximal biclique subgraphs from a graph is a computationally challenging problem, as the size of the output can become exponentially large with respect to the vertex number when the graph grows. In this paper, we efficiently enumerate them through the use of closed patterns of the adjacency matrix of the graph. For an undirected graph G without self-loops, we prove that 1) the number of closed patterns in the adjacency matrix of G is even, 2) the number of the closed patterns is precisely double the number of maximal biclique subgraphs of G, and 3) for every maximal biclique subgraph, there always exists a unique pair of closed patterns that matches the two vertex sets of the subgraph. Therefore, the problem of enumerating maximal bicliques can be solved by using efficient algorithms for mining closed patterns, which are algorithms extensively studied in the data mining field. However, this direct use of existing algorithms causes a duplicated enumeration. To achieve high efficiency, we propose an O(mn) time delay algorithm for a nonduplicated enumeration, in particular, for enumerating those maximal bicliques with a large size, where m and n are the number of edges and vertices of the graph, respectively. We evaluate the high efficiency of our algorithm by comparing it to state- of-the-art algorithms on three categories of graphs: randomly generated graphs, benchmarks, and a real-life protein interaction network. In this paper, we also prove that if self-loops are allowed in a graph, then the number of closed patterns in the adjacency matrix is not necessarily even, but the maximal bicliques are exactly the same as those of the graph after removing all the self-loops. [ABSTRACT FROM AUTHOR]

Identifying the rank of species in a complex ecosystem is a difficult task, since the rank of each species invariably depends on the interactions stipulated with other species through the adjacency matrix of the network. A common ranking method in economic and ecological networks is to sort the nodes such that the layout of the reordered adjacency matrix looks maximally nested with all nonzero entries packed in the upper left corner, called Nestedness Maximization Problem (NMP). Here we solve this problem by defining a suitable cost-energy function for the NMP which reveals the equivalence between the NMP and the Quadratic Assignment Problem, one of the most important combinatorial optimization problems, and use statistical physics techniques to derive a set of self-consistent equations whose fixed point represents the optimal nodes' rankings in an arbitrary bipartite mutualistic network. Concurrently, we present an efficient algorithm to solve the NMP that outperforms state-of-the-art network-based metrics and genetic algorithms. Eventually, our theoretical framework may be easily generalized to study the relationship between ranking and network structure beyond pairwise interactions, e.g. in higher-order networks. Species forming complex ecological or economic ecosystems are organized in hierarchies and the ranks of such species are determined by the adjacency matrix of their interaction network. We introduce a framework to calculate the ranks of species by finding the optimal permutation of rows and columns that makes the adjacency matrix maximally nested. [ABSTRACT FROM AUTHOR]

Let A(G) be the adjacency matrix of a graph G. Let s(vi) denote the row entries of A(G) corresponding to the vertex vi of G. The Hamming distance between the strings s(ui) and s(vi) is the number of positions in which their elements differ. The sum of Hamming distance between all the pairs of vertices is the Hamming index of a graph. In this paper, we study the Hamming distance between the strings generated by the adjacency matrix of various products of complete bipartite and complete graph. We also compute the Hamming index generated by the adjacency matrix of these graph products. [ABSTRACT FROM AUTHOR]

Let G be a simple graph, and ⃗G be an oriented graph of G with an orientation and skew-adjacency matrix S(⃗ G). Let λ1(⃗ G), λ2(⃗ G), . . ., λn(⃗ G) be the eigenvalues of S(⃗ G). The number Pn i=1 λki (⃗ G) (k = 0, 1, . . ., n - 1), denoted by Tk(⃗ G), is called the k-th skew spectral moment of ⃗ G, and T(⃗ G) = (T0(⃗ G), T1(⃗ G), . . ., Tn-1(⃗ G)) is the sequence of skew spectral moments of ⃗ G. Suppose ⃗G 1 and ⃗G 2 are two digraphs. We shall write ⃗G 1 ≺T ⃗G 2 (⃗G 1 comes before ⃗G 2 in a T-order) if for some k (1 ≤ k ≤ n-1), Ti(⃗G 1) = Ti(⃗G 2) (i = 0, 1, . . ., k-1) and Tk(⃗ G1) < Tk(⃗G 2) hold. For two given positive integers p and q with p ≤ q, we denote T p,q n = {T: T is a tree of order n with a (p, q)-bipartition }. In this paper, we discuss T-order among all trees in T p,q n . Furthermore, the last three trees, in the T-order, underlying graphs among T p,q n (4 ≤ p ≤ q) are characterized. [ABSTRACT FROM AUTHOR]

Spectral graph theory is like a special tool for understanding graphs. It helps us find patterns and connections in complex networks, using the magic of eigenvalues. Let G be the graph and A (G) be its adjacency matrix, then G is singular if the determinant of the adjacency matrix A (G) is 0, otherwise it is nonsingular. Within the realm of nonsingular graphs, there is the concept of property R , where each eigenvalue's reciprocal is also an eigenvalue of G. By introducing multiplicity constraints on both eigenvalues and their reciprocals, it becomes property SR. Similarly, the world of nonsingular graphs reveals property − R , where the negative reciprocal of each eigenvalue also finds a place within the spectrum of G. Moreover, when the multiplicity of each eigenvalue and its negative reciprocal is equal, this results in a graph with a property of − SR . Some classes of unweighted nonbipartite graphs are already constructed in the literature with the help of the complete graph K n and a copy of the path graph P 4 satisfying property R but not SR. This article takes this a step further. The main aim is to construct several weighted classes of graphs which satisfy property R but not SR. For this purpose, the weight functions are determined that enable these nonbipartite graph classes to satisfy the − SR and R properties, even if the unweighted graph does not satisfy these properties. Some examples are presented to support the investigated results. These examples explain how certain weight functions make these special types of graphs meet the properties R or − SR , even when the original graphs without weights do not meet these properties. [ABSTRACT FROM AUTHOR]

The rank of a digraph is defined as the rank of its adjacency matrix. In this paper we show how to find all digraphs of rank k from the reduced bipartite graphs of rank 2 k. In particular, since the bipartite graphs of rank 2 , 4 and 6 are known, then we characterize digraphs of rank 1 , 2 and 3. The results are based on rank-preserving operations on digraphs such as splitting and fusion of vertices or twin-deletion and vertex-multiplication. [ABSTRACT FROM AUTHOR]

Let G be a graph with adjacency matrix A(G), and let D(G) be the diagonal matrix of the degrees of G. For any real number α ∈ [0,1], Nikiforov defined the Aα-matrix of G as Aα (G) = αD(G) + (1 - α)A(G). The eigenvalues of the matrix Aα(G) form the Aα-spectrum of G. The Aα-spectral radius of G is the largest eigenvalue of Aα(G) denoted by ρα(G). In this paper, we propose the Aα--matrix of G as Aα-(G) = αD(G) + (α - 1)A(G), 0 ≤ α ≤ 1. Let the Aα--spectral radius of G be denoted by λα-(G), and let Sβα(G) and Sβα- (G) be the sum of the βth powers of the Aα and Aα- eigenvalues of G, respectively. We determine the Aα--spectra of some graphs and obtain some bounds of the Aα--spectral radius. Moreover, we establish a relationship between the Aα-spectral radius and Aα--spectral radius. Indeed, for α ∈ (1/2, 1), we show that λα- ≤ ρα, and we prove that if G is connected, then the equality holds if and only if G is bipartite. Employing this relation, we obtain some upper bounds of λα- (G), and we prove that the Aα--spectrum and Aα-spectrum are equal if and only if G is a bipartite connected graph. Furthermore, we generalize the relation established by S. Akbari et al. in (2010) as follows: for α ∈ [1/2, 1), if 0 < β ≤ 1 or 2 ≤ β ≤ 3, then Sβα(G) ≥ Sβα- (G), and if 1 ≤ β ≤ 2, then Sβα(G) ≤ Sβα-(G), where the equality holds if and only if G is a bipartite graph such that β ∉ {1,2,3}. [ABSTRACT FROM AUTHOR]

A vertex u ∈ V1 in a bipartite graph G(V1∪V2;E) is redundant if all the vertices of V2 that are adjacent to u are also adjacent to a vertex w (≠= u) in V1. In other words, NG(u) ⊆ NG(w). Such vertices increase the cost of the network (when it is a communication network) or increase the unnecessary membership of the network (when it is a social network). An ideal cost effective network is the one where there is no redundant vertex. In this article, we model the above type of networks using graphs and call them antichain graphs. We characterize such graphs and study their properties. We show that if G and H are antichain graphs then so is their cartesian product G x H. We design few more methods to construct new antichain graphs from the existing ones. We also present generating procedures, which generate some regular and biregular antichain graphs. We define a critical edge with reference to the antichain property. We also characterize the critical edge. [ABSTRACT FROM AUTHOR]

Graph entropy is an important measure of the evolution and complexity of networks. Bipartite graph is a special network and an important mathematical model for system resource allocation and management. In reality, a network system usually has obvious directionality. The direction of the network, or the movement trend of the network, can be described with spectrum index. However, little research has been done on the eigenvalue-based entropy of directed bipartite network. In this study, based on the adjacency matrix, the in-degree Laplacian matrix and the in-degree signless Laplacian matrix of directed bipartite graph, we defined the eigenvalue-based entropy for the directed bipartite network. Using the eigenvalue-based entropy, we described the evolution law of the directed bipartite network structure. Aiming at the direction and bipartite feature of the directed bipartite network, we improved the generation algorithm of the undirected network. We then constructed the directed bipartite nearest-neighbor coupling network, directed bipartite small-world network, directed bipartite scale-free network, and directed bipartite random network. In the proposed model, spectrum of those directed bipartite network is used to describe the directionality and bipartite property. Moreover, eigenvalue-based entropy is empirically studied on a real-world directed movie recommendation network, in which the law of eigenvalue-base entropy is observed. That is, if eigenvalue-based entropy value of the recommendation system is large, the evolution of movie recommendation network becomes orderless. While if eigenvalue-based entropy value is small, the structural evolution of the movie recommendation network tends to be regular. The simulation experiment shows that eigenvalue-based entropy value in the real directed bipartite network is between the values of a directed bipartite small world and a scale-free network. It shows that the real directed bipartite network has the structural property of the two typical directed bipartite networks. The coexistence of the small-world phenomena and the scale-free phenomena in the real network is consistent with the evolution law of typical network models. The experimental results show that the validity and rationality of the definition of eigenvalue-based entropy, which serves as a tool in the analysis of directed bipartite networks. [ABSTRACT FROM AUTHOR]

Signal processing on graphs finds applications in many areas. In recent years, renewed interest on this topic was kindled by two groups of researchers. Narang and Ortega constructed two-channel filter banks on bipartitie graphs described by Laplacians. Sandryhaila and Moura developed the theory of linear systems, filtering, and frequency responses for the case of graphs with arbitrary adjacency matrices, and showed applications in signal compression, prediction, etc. Inspired by these contributions, this paper extends classical multirate signal processing ideas to graphs. The graphs are assumed to be general with a possibly nonsymmetric and complex adjacency matrix. The paper revisits ideas, such as noble identities, aliasing, and polyphase decompositions in graph multirate systems. Drawing such a parallel to classical systems allows one to design filter banks with polynomial filters, with lower complexity than arbitrary graph filters. It is shown that the extension of classical multirate theory to graphs is nontrivial, and requires certain mathematical restrictions on the graph. Thus, classical noble identities cannot be taken for granted. Similarly, one cannot claim that the so-called delay chain system is a perfect reconstruction system (as in classical filter banks). It will also be shown that $M$ -partite extensions of the bipartite filter bank results will not work for $M$-channel filter banks, but a more restrictive condition called $M$-block cyclic property should be imposed. Such graphs are studied in detail. A detailed theory for $M$ -channel filter banks is developed in a companion paper. [ABSTRACT FROM PUBLISHER]

In this research paper we begin with study of family of n dimensional hyper cube graphs and establish some properties related to their distance, spectra, and multiplicities and associated eigen vectors and extend to bipartite double graphs[11]. In a more involved way since no complete characterization was available with experiential results in several inter connection networks on this spectra our work will add an element to existing theory. [ABSTRACT FROM AUTHOR]

Topological quantum field theories (TQFT) encode properties of quantum states in the topological features of abstract manifolds. One can use the topological avatars of quantum states to develop intuition about different concepts and phenomena of quantum mechanics. In this paper we focus on the class of simplest topologies provided by a specific TQFT and investigate what the corresponding states teach us about entanglement. These "planar connectome" states are defined by graphs of simplest topology for a given adjacency matrix. In the case of bipartite systems the connectomes classify different types of entanglement matching the classification of stochastic local operations and classical communication (SLOCC). The topological realization makes explicit the nature of entanglement as a resource and makes apparent a number of its properties, including monogamy and characteristic inequalities for the entanglement entropy. It also provides tools and hints to engineer new measures of entanglement and other applications. Here the approach is used to construct purely topological versions of the dense coding and quantum teleportation protocols, giving diagrammatic interpretation of the role of entanglement in quantum computation and communication. Finally, the topological concepts of entanglement and quantum teleportation are employed in a simple model of information retrieval from a causally disconnected region, similar to the interior of an evaporating black hole. [ABSTRACT FROM AUTHOR]

In the intelligent transportation system, the license information can be automatically recognized by the computer and the vehicle can be tracked. Red light running, illegal change of lanes, vehicle retrograde, and other illegal driving events are reasonably recorded. This is undoubtedly an effective help for the traffic police to relieve the huge work pressure. However, in China, a considerable number of vehicle tracking methods have certain limitations in resisting complex external environmental influences. The external environmental factors include but not limited to variable factors such as camera movement, jitter, and severe rain and snow. These factors cannot be controlled well, so the tracking accuracy is greatly reduced. In regard to this, this paper proposes an optimization method for moving vehicle tracking based on SPF. First, according to the size of the overlapping area of the motion area between the two images, the researcher can construct and simplify the vertex adjacency matrix that reflects the characteristics of the undirected bipartite graph. Then according to the corresponding relationship between the vertex adjacency matrix and the regional behavior and vehicle behavior, the researcher completes the regional behavior analysis and vehicle behavior analysis. On this basis, a particle filter vehicle tracking algorithm based on segmentation compensation is introduced, and the vector sum of the tracked segmentation area is used as the final position of the target vehicle. In this way, as many scattered particles fall on the target area as possible, which will greatly improve the efficiency of particle utilization, enhance tracking accuracy, and avoid the problem of tracking failure caused by too fast vehicle movement. Through experimental simulation, it can be seen that the method proposed in this paper can greatly enhance the vehicle tracking ability when tracking vehicles in "complex environments." [ABSTRACT FROM AUTHOR]

In this paper the unique graph with maximal index (i.e. the largest eigenvalue of the adjacency matrix) is identified among all connected bipartite graphs of order n and size n + k , under the assumption that k ≥ 0 and n ≥ k + 5 . [ABSTRACT FROM AUTHOR]

The second largest eigenvalue of a graph is an important algebraic parameter which is related with the expansion, connectivity and randomness properties of a graph. Expanders are highly connected sparse graphs. In coding theory, Expander codes are Error Correcting codes made up of bipartite expander graphs. In this paper, first we prove the interlacing of the eigenvalues of the adjacency matrix of the bipartite graph with the eigenvalues of the bipartite quotient matrices of the corresponding graph matrices. Then we obtain bounds for the second largest and second smallest eigenvalues. Since the graph is bipartite, the results for Laplacian will also hold for Signless Laplacian matrix. We then introduce a new method called vertex-split of a bipartite graph to construct asymptotically good expander codes with expansion factor D/2 < α < D and ϵ < 1/2 and prove a condition for the vertex-split of a bipartite graph to be k-connected with respect to λ2. Further, we prove that the vertex-split of G is a bipartite expander. Finally, we construct an asymptotically good expander code whose factor graph is a graph obtained by the vertex-split of a bipartite graph. [ABSTRACT FROM AUTHOR]

Recent advancements in spatial transcriptomics technology have revolutionized our ability to comprehensively characterize gene expression patterns within the tissue microenvironment, enabling us to grasp their functional significance in a spatial context. One key field of research in spatial transcriptomics is the identification of spatial domains, which refers to distinct regions within the tissue where specific gene expression patterns are observed. Diverse methodologies have been proposed, each with its unique characteristics. As the availability of spatial transcriptomics data continues to expand, there is a growing need for methods that can integrate information from multiple slices to discover spatial domains. To extend the applicability of existing single-slice analysis methods to multi-slice clustering, we introduce BiGATAE (Bipartite Graph Attention Auto Encoder) that leverages gene expression information from adjacent tissue slices to enhance spatial transcriptomics data. BiGATAE comprises two steps: aligning slices to generate an adjacency matrix for different spots in consecutive slices and constructing a bipartite graph. Subsequently, it utilizes a graph attention network to integrate information across different slices. Then it can seamlessly integrate with pre-existing techniques. To evaluate the performance of BiGATAE, we conducted benchmarking analyses on three different datasets. The experimental results demonstrate that for existing single-slice clustering methods, the integration of BiGATAE significantly enhances their performance. Moreover, single-slice clustering methods integrated with BiGATAE outperform methods specifically designed for multi-slice integration. These results underscore the proficiency of BiGATAE in facilitating information transfer across multiple slices and its capacity to broaden the applicability and sustainability of pre-existing methods. [ABSTRACT FROM AUTHOR]

Abstract: In this paper we obtain several characterizations of the adjacency matrix of a probe interval graph. In course of this study we describe an easy method of obtaining interval representation of an interval bigraph from its adjacency matrix. Finally, we note that if we add a loop at every probe vertex of a probe interval graph, then the Ferrers dimension of the corresponding symmetric bipartite graph is at most 3. [ABSTRACT FROM AUTHOR]

In this paper we determine the unique graph with minimal least eigenvalue (of the adjacency matrix) within the set of connected graphs of fixed order n and size m , whenever m = ⌈ n 2 ⌉ ⌊ n 2 ⌋ + a , where a is a fixed integral constant in [ 1 , ⌈ n 2 ⌉ − 1 ] . [ABSTRACT FROM AUTHOR]

The goal of this contribution is to reveal the analytical framework and synthesis guidelines for frontal-attacking targets (FRATs) and flankattacking targets (FLATs) from the point of view of a graph as a mathematical object. The final outcome of this study are three graph models that in many ways describe the shooting targets under consideration. The first graph model characterizes the structure of connections between the vertices using an undirected graph. The model showed that the complexity of silhouettes leads to an increase of the path in the graph and growth of the complexity of its internal structure. The second graph model allows the analysis of the connectivity of the graph vertices. In this case, a bipartite graph is used. As a result, the reviewed FRATs and FLATs are described by the same graph. The second model showed its indifference to the types of the used graphic primitives (GPs). The third graph model was developed for the analysis of the common borders of the neighboring GPs and it uses a bipartite graph. It is also indifferent to the types of the used GPs, but it takes into account the length of the common borders. The third model describes FRATs/FLATs groups in the same way. When using I-III models, one can design GPs and carry out the synthesis of new targets. A full group of flank-attacking targets consisting of five silhouettes and their GPs is offered. [ABSTRACT FROM AUTHOR]

A graph is integral if the spectrum (of its adjacency matrix) consists entirely of integers. The problem of determining all non-regular bipartite integral graphs with maximum degree four which do not have ±1 as eigenvalues was posed in K.T. Baliéska, S.K. Simić, K.T. Zwierzyński: Which nonregular bipartite integral graphs with maximum degree four do not have ±1 as eigenvalues? Discrete Math., 286 (2004), 15-25. Here we revisit this problem, and provide its complete solution using mostly the theoretical arguments. [ABSTRACT FROM AUTHOR]

Abstract: The rank of a graph is that of its adjacency matrix. A graph is called reduced if it has no isolated vertices and no two vertices with the same set of neighbors. We determine the maximum order of reduced trees as well as bipartite graphs with a given rank and characterize those graphs achieving the maximum order. [Copyright &y& Elsevier]

Abstract: The problem of identifying those simple, undirected graphs with vertices and edges that have the smallest minimum eigenvalue of the adjacency matrix is considered. Several general properties of the minimizing graphs are described. These strongly suggest bipartition, to the extent possible for the number of edges. In the bipartite case, the precise structure of the minimizing graphs is given for a number of infinite classes. [Copyright &y& Elsevier]

Abstract: A spectral graph theory is a theory in which graphs are studied by means of eigenvalues of a matrix which is in a prescribed way defined for any graph. This theory is called -theory. We outline a spectral theory of graphs based on the signless Laplacians and compare it with other spectral theories, in particular to those based on the adjacency matrix and the Laplacian . As demonstrated in the first part, the -theory can be constructed in part using various connections to other theories: equivalency with -theory and -theory for regular graphs, common features with -theory for bipartite graphs, general analogies with -theory and analogies with -theory via line graphs and subdivision graphs. In this part, we introduce notions of enriched and restricted spectral theories and present results on integral graphs, enumeration of spanning trees, characterizations by eigenvalues, cospectral graphs and graph angles. [Copyright &y& Elsevier]

Counting short cycles in bipartite graphs is a fundamental problem of interest in many fields including the analysis and design of low-density parity-check (LDPC) codes. There are two computational approaches to count short cycles (with length smaller than $2g$ , where $g$ is the girth of the graph) in bipartite graphs. The first approach is applicable to a general (irregular) bipartite graph, and uses the spectrum $\{\eta _{i}\}$ of the directed edge matrix of the graph to compute the multiplicity $N_{k}$ of $k$ -cycles with $k < 2g$ through the simple equation $N_{k} = \sum _{i} \eta _{i}^{k}/(2k)$. This approach has a computational complexity $\mathcal {O}(|E|^{3})$ , where $|E|$ is number of edges in the graph. The second approach is only applicable to bi-regular bipartite graphs, and uses the spectrum $\{\lambda _{i}\}$ of the adjacency matrix (graph spectrum) and the degree sequences of the graph to compute $N_{k}$. The complexity of this approach is $\mathcal {O}(|V|^{3})$ , where $|V|$ is number of nodes in the graph. This complexity is less than that of the first approach, but the equations involved in the computations of the second approach are complex and tedious, particularly for $k \geq g+6$. In fact, the computational complexity of the equations increases exponentially with $k$. In this paper, we establish an analytical relationship between the two spectra $\{\eta _{i}\}$ and $\{\lambda _{i}\}$ for bi-regular bipartite graphs. Through this relationship, the former spectrum can be derived from the latter through simple equations with computational complexity constant in $k$. This allows the computation of $N_{k}$ using $N_{k} = \sum _{i} \eta _{i}^{k}/(2k)$ but with a complexity of $\mathcal {O}(|V|^{3})$ rather than $\mathcal {O}(|E|^{3})$. [ABSTRACT FROM AUTHOR]

We give a new construction of Ramanujan graphs using a generalized type of covering graph called a weighted covering graph. For a given prime p the basic construction produces bipartite Ramanujan graphs with 4p vertices and degrees 2N where roughly p + 1 - √2p} < N ≤ p We then give generalizations to produce Ramanujan graphs of other sizes and degrees as well as general results about base graphs which have weighted covers that satisfy their Ramanujan bounds. To do the construction, we define weighted covering graphs and distinguish a subclass of Galois weighted covers that allows for block diagonalization of the adjacency matrix. The specific construction allows for easy computation of the resulting blocks. The Gershgorin Circle Theorem is then used to compute the Ramanujan bounds on the spectra. [ABSTRACT FROM AUTHOR]

We consider only connected bipartite graphs G with a unique perfect matching M . Let G w be the weighted graph obtained from G by giving weights to its edges using the positive weight function w : E ( G ) → ( 0 , ∞ ) such that w ( e ) = 1 for each e ∈ M . An unweighted graph G may be viewed as a weighted graph with the weight function w ≡ 1 . A weighted graph G w is nonsingular if its adjacency matrix A ( G w ) is nonsingular. The inverse of a nonsingular weighted graph G w is the unique weighted graph whose adjacency matrix is similar to the inverse of the adjacency matrix A ( G w ) via a diagonal matrix of ±1s. By G / M we denote the graph obtained from G by contracting each edge of M to a single vertex. It is known that if G / M is bipartite, then G w is invertible for each weight function w. In this article, we consider the converse of this result and show that if G w is invertible for each w, then the graph G / M is bipartite. We also supply exact conditions under which G w is invertible for one w will force that the graph G / M is bipartite. [ABSTRACT FROM AUTHOR]

Copyright of Kuwait Journal of Science is the property of Kuwait University, Academic Publication Council and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Let D G ˜ be an n -vertex weighted mixed graph with Hermitian-adjacency matrix H (D G ˜ ). The characteristic polynomial of the weighted mixed graph D G ˜ is defined as ϕ (D G ˜ , λ) = det ⁡ (λ I n − H (D G ˜ )) = ∑ r = 0 n α r λ n − r and the H -rank of D G ˜ , written as r k (D G ˜ ) , is the rank of H (D G ˜ ). In this paper, we begin by interpreting all the coefficients of the characteristic polynomial ϕ (D G ˜ , λ). Then we establish recurrences for the characteristic polynomial ϕ (D G ˜ , λ). By these obtained results, as a unified approach, some main results obtained in Hou and Lei (2011) [13] , Gong and Xu (2012) [10] , Liu and Li (2015) [18] can be deduced consequently. Furthermore, for a weighted mixed bipartite cactus graph D G ˜ , we give a necessary and sufficient condition for r k (D G ˜ ) = 2 t , where t is any integer no greater than the matching number of G. Finally, as an application of our results, we study the minimum H -rank problem, determining the minimum H -rank of bipartite cactus graphs. [ABSTRACT FROM AUTHOR]

Targeted drugs have been applied to the treatment of cancer on a large scale, and some patients have certain therapeutic effects. It is a time-consuming task to detect drug–target interactions (DTIs) through biochemical experiments. At present, machine learning (ML) has been widely applied in large-scale drug screening. However, there are few methods for multiple information fusion. We propose a multiple kernel-based triple collaborative matrix factorization (MK-TCMF) method to predict DTIs. The multiple kernel matrices (contain chemical, biological and clinical information) are integrated via multi-kernel learning (MKL) algorithm. And the original adjacency matrix of DTIs could be decomposed into three matrices, including the latent feature matrix of the drug space, latent feature matrix of the target space and the bi-projection matrix (used to join the two feature spaces). To obtain better prediction performance, MKL algorithm can regulate the weight of each kernel matrix according to the prediction error. The weights of drug side-effects and target sequence are the highest. Compared with other computational methods, our model has better performance on four test data sets. [ABSTRACT FROM AUTHOR]

Clustering large hyperspectral images (HSIs) is a very challenging problem because large HSIs have high dimensionality, large spectral variability, and large computational and memory consumption. Recently, sparse subspace clustering (SSC) has achieved remarkable success in HSI clustering. However, most SSC-based methods suffer from the following bottlenecks for large HSIs: 1) high computational consumption and memory space during the construction of the similarity matrix and decomposition of the graph Laplacian matrix and 2) failure to capture the relationships among dictionary atoms, sparse coefficients, and hyperspectral pixels. To address these challenges, we propose a novel algorithm that extends SSC to cocluster large HSIs, called bipartite graph partition with graph nonnegative matrix factorization (BGP-GNMF). Specifically, to fully explore the characteristics of the spectral and spatial contexts in HSIs, we propose a novel superpixel and pixel coclustering framework with bipartite graph partitioning in the joint sparse representation domain, where superpixel-based dictionary atoms are defined as disjoint vertex sets of the bipartite graph and the joint sparsity representation is mapped into the adjacency matrix of the undirected bipartite graph. To overcome the challenges of high computational consumption and large memory space for large HSIs, the bipartite graph partition with orthonormal constrained nonnegative matrix factorization is proposed to simultaneously cluster the structured dictionary atoms and hyperspectral pixels with an indicator matrix. Finally, to exploit the intrinsic geometry of HSIs, we incorporate manifold regularization into the bipartite graph partition to improve final clustering accuracy. The effectiveness and efficiency of the proposed method are verified on three classical HSIs, and the experimental results illustrate the superiority of the proposed method compared with other state-of-the-art HSI clustering methods. [ABSTRACT FROM AUTHOR]

Counting short cycles in bipartite graphs is a fundamental problem of interest in the analysis and design of low-density parity-check codes. The vast majority of research in this area is focused on algorithmic techniques. Most recently, Blake and Lin proposed a computational technique to count the number of cycles of length $\boldsymbol {g}$ in a bi-regular bipartite graph, where $\boldsymbol {g}$ is the girth of the graph. The information required for the computation is the node degree and the multiplicity of the nodes on both sides of the partition, as well as the eigenvalues of the adjacency matrix of the graph (graph spectrum). In this paper, the result of Blake and Lin is extended to compute the number of cycles of length $\boldsymbol {g} + \textbf {2}, \ldots, \textbf {2}\boldsymbol {g}-\textbf {2}$ , for bi-regular bipartite graphs, as well as the number of 4-cycles and 6-cycles in irregular and half-regular bipartite graphs, with $\boldsymbol {g} \geq \textbf {4}$ and $\boldsymbol {g} \geq \textbf {6}$ , respectively. [ABSTRACT FROM AUTHOR]

We consider only simple graphs. Consider connected bipartite graphs with unique perfect matchings such that the graph obtained by contracting all matching edges is also bipartite. On the class H g of such graphs G the equivalence of the following statements are known. i) The reciprocal of the spectral radius of the adjacency matrix A ( G ) is the least positive eigenvalue of the adjacency matrix. ii) The graph is isomorphic to its inverse, where the inverse of a graph G is the unique weighted graph whose adjacency matrix is similar to the inverse of the adjacency matrix A ( G ) via a diagonal matrix of ±1s. iii) The graph has the reciprocal eigenvalue property, that is, the reciprocal of each eigenvalue of the adjacency matrix A ( G ) is also an eigenvalue of A ( G ) . iv) The graph has the strong reciprocal eigenvalue property, that is, the reciprocal of each eigenvalue of the adjacency matrix A ( G ) is also an eigenvalue of A ( G ) and they both have the same multiplicities. v) The graph is a corona graph, that is, it is obtained by taking a bipartite graph and then by inserting a new adjacent vertex of degree one at each vertex. It is known that the statements iii) and iv) are not equivalent, if we allow nonbipartite graphs. However, the equivalence of these two is not yet known for the class of bipartite graphs with unique perfect matchings, where we relax the condition of bipartiteness of the contracted graph. In this article, we establish the equivalence of the first four statements for a class larger than H g . We then supply a constructive structural description of those graphs. [ABSTRACT FROM AUTHOR]

Abstract: A graph is called reflexive if its second largest eigenvalue does not exceed 2. In this paper, we determine all reflexive bipartite regular graphs. Any bipartite regular graph of degree at most 2 is reflexive as well as its bipartite complement. Apart from them, there is a finite number of resulting graphs. [Copyright &y& Elsevier]

Let G be a graph with adjacency matrix A ( G ) and let D ( G ) be the diagonal matrix of the degrees of G . For every real α ∈ [ 0 , 1 ] , write A α ( G ) for the matrix A α ( G ) = α D ( G ) + ( 1 − α ) A ( G ) . Let α 0 ( G ) be the smallest α for which A α ( G ) is positive semidefinite. It is known that α 0 ( G ) ≤ 1 / 2 . The main results of this paper are: (1) if G is d -regular then α 0 = − λ min ( A ( G ) ) d − λ min ( A ( G ) ) , where λ min ( A ( G ) ) is the smallest eigenvalue of A ( G ) ; (2) G contains a bipartite component if and only if α 0 ( G ) = 1 / 2 ; (3) if G is r -colorable, then α 0 ( G ) ≥ 1 / r . [ABSTRACT FROM AUTHOR]

Abstract: We derive some structural and spectral properties of regular bipartite graphs with three distinct non-negative eigenvalues. Next, we consider the relations between these graphs and two-class partially balanced incomplete block designs, and we present a number of situations when the graphs we consider are in fact the incidence graphs of those designs. As a consequence, we give a several constructions of connected regular bipartite graphs with six distinct eigenvalues, and we also determine all such graphs with degree 3, and all such graphs on at most 20 vertices. [Copyright &y& Elsevier]

Abstract: We determine all trees whose second largest eigenvalue does not exceed . Next, we consider two classes of bipartite graphs, regular and semiregular, with small number of distinct eigenvalues. For all graphs considered we determine those whose second largest eigenvalue is equal to . Some additional results are also given. [Copyright &y& Elsevier]

Abstract: In this paper we characterize the unique graph whose least eigenvalue attains the minimum among all connected graphs of fixed order and given number of cut vertices, and then obtain a lower bound for the least eigenvalue of a connected graph in terms of the number of cut vertices. During the discussion we also get some results for the spectral radius of a connected bipartite graph and its upper bound. [Copyright &y& Elsevier]

Abstract: In 1977, Ganter and Teirlinck proved that any matrix with nonzero elements can be partitioned into four submatrices of order of which at most two contain nonzero elements. In 1978, Kramer and Mesner conjectured that any matrix with nonzero elements can be partitioned into submatrices of order of which at most contain nonzero elements. In 1995, Brualdi et al. showed that this conjecture is true if , or . They also found a counterexample of this conjecture for , , and . When , Rho showed that this conjecture is true if . When and , we show that this conjecture is true if or . As a result, we show that when , this conjecture is true if also. [Copyright &y& Elsevier]

Abstract: For , , a Bethe tree is a rooted tree with levels which the root vertex has degree , the vertices from level to have degree and the vertices at the level are pendent vertices. So et al, using a theorem by Ky Fan have obtained both upper and lower bounds for the Laplacian energy of bipartite graphs. We shall employ the above mentioned theorem to obtain new and improved bounds for the Laplacian energy in the case of Bethe trees. [Copyright &y& Elsevier]

Abstract: We say that two graphs and with the same vertex set commute if their adjacency matrices commute. In this paper, we find all integers such that the complete bipartite graph is decomposable into commuting perfect matchings or commuting Hamilton cycles. We show that there are at most linearly independent commuting adjacency matrices of size ; and if this bound occurs, then there exists a Hadamard matrix of order . Finally, we determine the centralizers of some families of graphs. [Copyright &y& Elsevier]

The singular values of a matrix A are defined as the square roots of the eigenvalues of A ⁎ A , and the energy of A denoted by E (A) is the sum of its singular values. The energy of a graph G , E (G) , is defined as the sum of absolute values of the eigenvalues of its adjacency matrix. In this paper, we prove that if A is a Hermitian matrix with the block form A = ( B D D ⁎ C ) , then E (A) ≥ 2 E (D). Also, we show that if G is a graph and H is a spanning subgraph of G such that E (H) is an edge cut of G , then E (H) ≤ E (G) , i.e., adding any number of edges to each part of a bipartite graph does not decrease its energy. Let G be a connected graph of order n and size m with the adjacency matrix A. It is well-known that if G is a bipartite graph, then E (G) ≥ 4 m + n (n − 2) | det ⁡ (A) | 2 n . Here, we improve this result by showing that the inequality holds for all connected graphs of order at least 7. Furthermore, we improve a lower bound for E (G) given in Oboudi (2019) [14]. [ABSTRACT FROM AUTHOR]