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 mixed graph and α ∈ [ 0 , 1 ]. Let D ˆ (G ˆ) and A ˆ (G ˆ) be the diagonal matrix of vertex degrees and the mixed adjacency matrix of G ˆ , respectively. The α -mixed adjacency matrix of G ˆ is the matrix A ˆ α (G ˆ) = α D ˆ (G ˆ) + (1 − α) A ˆ (G ˆ). We study some properties of A ˆ α (G ˆ) associated with some type of mixed graphs, namely quasi-bipartite and pre-bipartite mixed graphs. A spectral characterization for pre-bipartite and some class of quasi-bipartite mixed graphs is given. For a mixed graph G ˆ we exploit the problem of finding the smallest α for which A ˆ α (G ˆ) is positive semi-definite. This problem was proposed by Nikiforov in the context of undirected graphs. It is proven here that, for a mixed graph this number is not greater than 1 2 and that a connected mixed graph G ˆ with n ≥ 2 is quasi-bipartite if and only if this number is exactly 1 2. The spread of the α -mixed adjacency matrix is the difference among the largest and the smallest α -mixed adjacency eigenvalue. Upper and lower bounds for the spread of the α - mixed adjacency matrix are obtained. The α -mixed Estrada index of G ˆ is the sum of the exponentials of the eigenvalues of A ˆ α (G ˆ). In this paper, bounds for the eigenvalues of A ˆ α (G ˆ) are established and, using these bounds some sharp bounds on the mixed Estrada index of A ˆ α (G ˆ) are presented. [ABSTRACT FROM AUTHOR]

A complex unit gain graph is a simple graph in which each orientation of an edge is given a complex number with modulus 1 and its inverse is assigned to the opposite orientation of the edge. In this article, first we establish bounds for the eigenvalues of the complex unit gain graphs. Then we study some of the properties of the adjacency matrix of a complex unit gain graph in connection with the characteristic and the permanental polynomials. Then we establish spectral properties of the adjacency matrices of complex unit gain graphs. In particular, using Perron–Frobenius theory, we establish a characterization for bipartite graphs in terms of the set of eigenvalues of a gain graph and the set of eigenvalues of the underlying graph. Also, we derive an equivalent condition on the gain so that the eigenvalues of the gain graph and the eigenvalues of the underlying graph are the same. [ABSTRACT FROM AUTHOR]

The classical Pauli group can be obtained as the central product of the dihedral group of 8 elements with the cyclic group of order 4. Inspired by this characterization, we introduce the notion of central product of Cayley graphs, which allows to regard the Cayley graph of a central product of groups as a quotient of the Cartesian product of the Cayley graphs of the factor groups. We focus our attention on the Cayley graph C a y (P n , S P n ) of the generalized Pauli group P n on n -qubits; in fact, P n may be decomposed as the central product of finite 2-groups, and a suitable choice of the generating set S P n allows us to recognize the structure of central product of graphs in C a y (P n , S P n ). Using this approach, we are able to recursively construct the adjacency matrix of C a y (P n , S P n ) for each n ≥ 1 , and to explicitly describe its spectrum and the associated eigenvectors. It turns out that C a y (P n , S P n ) is a (3 n + 2) -regular bipartite graph on 4 n + 1 vertices, and it has integral spectrum. This is a highly nontrivial property if one considers that, by choosing as a generating set for P 1 the three classical Pauli matrices, one gets the so-called Möbius-Kantor graph, belonging to the class of generalized Petersen graphs, whose spectrum is not integral. [ABSTRACT FROM AUTHOR]

In 2010, Butler introduced the unfolding operation on a bipartite graph to produce two bipartite graphs, which are cospectral for the adjacency and the normalized Laplacian matrices. In this article, we describe how the idea of unfolding a bipartite graph with respect to another bipartite graph can be extended to nonbipartite graphs. In particular, we describe how unfoldings involving reflexive bipartite, semi-reflexive bipartite, and multipartite graphs are used to obtain cospectral nonisomorphic graphs for the adjacency matrix. [ABSTRACT FROM AUTHOR]

Let G be a simple graph with the adjacency matrix A (G) , and let τ (G) denote the smallest positive eigenvalue of A (G). Let G n be the class of all connected bipartite graphs on n = 2 k vertices with a unique perfect matching. In this article, we characterize the graphs G in G n such that τ (G) does not exceed 1 2. Using the above characterization, we obtain the unique graphs in G n with the maximum and the second maximum τ , respectively. Further, we prove that the largest and the second largest limit points of the smallest positive eigenvalues of bipartite graphs with a unique perfect matching are 1 2 and the reciprocal of α 3 1 2 + α 3 − 1 2 , respectively, where α 3 is the largest root of x 3 − x − 1. [ABSTRACT FROM AUTHOR]

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]

The biclique partition number of a graph G, denoted by bp(G), is the minimum number of complete bipartite subgraphs are needed to be representing all edges of G. A graph G is called an eigensharp graph if it is satisfying bp(G) = max{i-(A(G)), i+(A(G))} where i-(A(G)) and i+(A(G)) are the number of negative and positive eigenvalues of the adjacency matrix of G, respectively. In this paper, we are interested in studying some special graphs in terms of having the property of eigensharp. We show that the barbell graph, the sun graph, the friendship graph and their complements have the property of eigensharp. [ABSTRACT FROM AUTHOR]

In this paper, continuous-time quantum walk is discussed based on the view of quantum probability, i.e. the quantum decomposition of the adjacency matrix A of graph. Regard adjacency matrix A as Hamiltonian which is a real symmetric matrix with elements 0 or 1, so we regard  e − i t A  as an unbiased evolution operator, which is related to the calculation of probability amplitude. Combining the quantum decomposition and spectral distribution  μ  of adjacency matrix A, we calculate the probability amplitude reaching each stratum in continuous-time quantum walk on complete bipartite graphs, finite two-dimensional lattices, binary tree, N -ary tree and N -fold star power G ⋆ N . Of course, this method is also suitable for studying some other graphs, such as growing graphs, hypercube graphs and so on, in addition, the applicability of this method is also explained. [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]

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]

An oriented graph is called singular or nonsingular according as its adjacency matrix is singular or nonsingular. In this note, by a new approach, we determine the singularity of oriented quasi-trees. The main results of Chen et al. ['Singularity of oriented graphs from several classes', Bull. Aust. Math. Soc. 102 (1) (2020), 7–14] follow as corollaries. Furthermore, we give a necessary condition for an oriented bipartite graph to be nonsingular. By applying this condition, we characterise nonsingular oriented bipartite graphs $B_{m,n}$ when $\min \{m,n\}\leq 3$. [ABSTRACT FROM AUTHOR]

The complex adjacency matrix A C (G) for a multidigraph G is introduced in Barik and Sahoo (AKCE Int J Graphs Comb 17(1):466–479, 2020). We study the rank of multidigraphs corresponding to the complex adjacency matrix and call it A C -rank. It is known that a connected graph G has rank 2 if and only if G is a complete bipartite graph, and has rank 3 if and only if it is a complete tripartite graph (Cheng in Electron J Linear Algebra 16:60–67, 2007). We observe that these results hold as special cases for multidigraphs but are not sufficient. In this article, we characterize all multidigraphs with A C -rank 2 and 3, respectively. [ABSTRACT FROM AUTHOR]

Let G be a graph and d i be the degree of a vertex v i in G. For a symmetric real function f (x , y) , one can get an edge-weighted graph in such a way that for each edge v i v j of G , the weight of v i v j is assigned by f (d i , d j). Hence, we have a weighted adjacency matrix A f (G) of G , in which the ij -entry is equal to f (d i , d j) if v i v j ∈ E (G) and 0 otherwise. In this paper, we use a unified approach to deal with the spectral properties of A f (G) for f (x , y) to be the functions of graphical or topological function-indices. Firstly, we obtain uniform interlacing inequalities for the weighted adjacency eigenvalues. For the edge-weight functions defined by almost a half of popularly used topological indices, it can be shown that our inequalities cannot be improved. Secondly, we establish a uniform equivalent condition for a connected graph G to have m distinct weighted adjacency eigenvalues. As an application, a combinatorial characterization for a graph to have two and three distinct weighted adjacency eigenvalues is presented, respectively. Moreover, bipartite graphs and unicyclic graphs with three distinct weighted adjacency eigenvalues are characterized. This paper attempts to unify the spectral study for weighted adjacency matrices of graphs with degree-based edge-weights. [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]

Let G be a simple connected graph and A (G) be the adjacency matrix of G. A diagonal matrix with diagonal entries ±1 is called a signature matrix. If A (G) is nonsingular and X = S A (G) − 1 S − 1 is entrywise nonnegative for some signature matrix S , then X can be viewed as the adjacency matrix of a unique weighted graph. It is called the inverse of G , denoted by G +. A graph G is said to have the reciprocal eigenvalue property (property(R)) if A (G) is nonsingular, and 1 λ is an eigenvalue of A (G) whenever λ is an eigenvalue of A (G). Further, if λ and 1 λ have the same multiplicity for each eigenvalue λ , then G is said to have the strong reciprocal eigenvalue property (property (SR)). It is known that for a tree T , the following conditions are equivalent: a) T + is isomorphic to T , b) T has property (R), c) T has property (SR) and d) T is a corona tree (it is a tree which is obtained from another tree by adding a new pendant at each vertex). Studies on the inverses, property (R) and property (SR) of bipartite graphs are available in the literature. However, their studies for the non-bipartite graphs are rarely done. In this article, we study the inverse and property (SR) for non-bipartite graphs. We first introduce an operation, which helps us to study the inverses of non-bipartite graphs. As a consequence, we supply a class of non-bipartite graphs for which the inverse graph G + exists and G + is isomorphic to G. It follows that each graph G in this class has property (SR). [ABSTRACT FROM AUTHOR]

Let G be a simple connected graph and A (G) be the adjacency matrix of G. The graph G is said to have the reciprocal eigenvalue property (R) if A (G) is nonsingular and 1 λ is an eigenvalue of A (G) whenever λ is an eigenvalue of A (G). Further, if λ and 1 λ have the same multiplicity, for each eigenvalue λ , then G is said to have the strong reciprocal eigenvalue property (SR). Till date, all the classes of bipartite graphs that are found to have property (R), are found to have property (SR) and it is not known whether these two properties are equivalent even for the bipartite graphs with a unique perfect matching. Among nonbipartite graphs, there is only one known graph class for which these two properties are not equivalent. In this article, we construct some more classes of nonbipartite graphs with property (R) but not (SR). [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]

Let G be a simple graph with the adjacency matrix $ A(G) $ A (G). Let $ \tau (G) $ τ (G) denote the smallest positive eigenvalue of $ A(G) $ A (G). In 1990, Pavlíková and Kr $ \breve{c} $ c ˘ -Jediný proved that among all nonsingular trees on n = 2m vertices, the comb graph (obtained by taking a path on m vertices and adding a new pendant vertex to every vertex of the path) has the maximum τ value. We consider the problem for unicyclic graphs. Let $ \mathscr {U} $ U denote the class of all connected bipartite unicyclic graphs with a unique perfect matching, and for each $ m\geq ~3 $ m ≥ 3 , let $ \mathscr {U}_n $ U n be the subclass of $ \mathscr {U} $ U with graphs on n = 2m vertices. We first obtain the classes of unicyclic graphs U in $ \mathscr {U} $ U such that $ \tau (U)\leq \sqrt {2}-1 $ τ (U) ≤ 2 − 1. We then find the unique graph $ U_o^n $ U o n (resp. $ U_e^n $ U e n ) having the maximum τ value among all graphs in $ \mathscr {U}_n $ U n when m is odd (resp. when m is even). Finally, we prove that $ U_o^6 $ U o 6 (the graph obtained from a cycle of order 4, by adding two pendants to two adjacent vertices) is the graph with maximum τ value among all graphs in $ \mathscr {U} $ U . As a consequence, we obtain a sharp upper bound for $ \tau (U) $ τ (U) when $ U\in \mathscr {U} $ U ∈ U . [ABSTRACT FROM AUTHOR]

At present, network representation learning methods are mostly aimed at homogeneous networks, ignoring the particularity of attributed bipartite networks and the motifs structure of networks. In order to solve the above problems, this paper proposes an attributed bipartite graph neural network with motifs information for network representation learning (MABG). MABG adjusts the edge weights by the number of butterfly motifs formed by two nodes in the network, to construct the motifs weight matrix and obtain the attributed bipartite network adjacency matrix with motifs information. Then two different strategies are adopted to capture the explicit and implicit messages in the bipartite network. For explicit relationships, a message-passing mechanism is operated between different types of nodes. For implicit relationships, a message alignment mechanism is used in nodes of the same type. An adversarial model is implemented to minimize the difference between input attributes and explicit relationship representations. Finally, a cascaded framework is proposed to capture high-order network information and obtain the final node representation. Extensive experiments are conducted in recommended tasks on four real-world datasets. The results demonstrate the effectiveness of MABG compared with other state-of-art methods. [ABSTRACT FROM AUTHOR]

In [A note about cospectral graphs for the adjacency and normalized Laplacian matrices. Linear Multilinear Algebra. 2010;58(3-4):387–390], Butler constructed a family of bipartite graphs, which are cospectral for both the adjacency and the normalized Laplacian matrices. In this article, we extend this construction for generating larger classes of bipartite graphs, which are cospectral for both the adjacency and the normalized Laplacian matrices. Also, we provide a couple of constructions of non-bipartite graphs, which are cospectral for the adjacency matrices but not necessarily for the normalized Laplacian matrices. [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]

Let G be a graph, and let $ A(G) $ A (G) be the adjacency matrix of G. The computation of permanent of $ A(G) $ A (G) is #p-complete. Computing permanent of $ A(G) $ A (G) is of great interest in quantum chemistry, statistical physics, among other disciplines. In this paper, we characterize the ordering of permanents of adjacency matrices of all graphs obtained from regular complete bipartite graph $ K_{p, p} $ K p , p by deleting six edges. As an application, we show that all graphs with a perfect matching obtained from $ K_{p, p} $ K p , p with six edges deleted are determined by their permanental polynomials. [ABSTRACT FROM AUTHOR]

Networks, consisting of vertices connected by edges, are an important mathematical concept used to describe relationships between people, roads between cities, reactions between chemicals, and many other interactions. Such a network can be created by extracting cocrystals from the Cambridge Structural Database (CSD). This network describes which compounds can form cocrystals together and can, for example, be used to predict new cocrystals using link-prediction techniques. Bipartiteness is an important property of some networks wherein the vertices can be separated into two groups such that edges only point from one group to the other. Knowing whether a network is bipartite can make studying its structure considerably easier. If a network is nearly bipartite except for a number of outlying edges, one might want to identify and remove those edges, thereby bipartising the network. The CSD cocrystal network was previously found to be close to bipartiteness. Truly bipartising it could improve the accuracy of link-prediction and give insight into the hidden structure of the network. Many algorithms exist for exactly finding the optimal bipartisation for a nearly-bipartite network, but the time it takes to complete such algorithms increases exponentially with the size of the problem. In some cases, an exact solution is unnecessary and a 'good enough' bipartisation is sufficient. We have developed an algorithm that can find a near-optimal bipartisation within reasonable time, even for very large networks, and used it to unravel the structure of the CSD cocrystal network. We obtained a bipartisation that leaves 96% of the network intact, and we were able to identify 'universal' coformers that do not conform to the bipartite nature of the network. By applying a clustering algorithm to the bipartised network, we were also able to identify anticommunities of coformers. [ABSTRACT FROM AUTHOR]

Abstract Let G be a graph on n vertices and η 1 , η 2 , ... , η n the eigenvalues of its extended adjacency matrix. The extended Estrada index EE ex is defined as the sum of the terms e η i , i = 1 , 2 , ... , n. In this paper we show the extended Estrada index of the complete bipartite graphs and the friendship graphs. Also the relationship of the extended Estrada index between the m -splitting, m -shadow graphs and the original graphs are obtained. [ABSTRACT FROM AUTHOR]

Abstract An expression of the coefficient of immanantal polynomial of an n × n matrix is present. Moreover, we give expressions of the coefficient of immanantal polynomials of combinatorial matrices (adjacency matrix, Laplacian matrix, signless Laplacian matrix). As applications, we show that the immanantal polynomials for Laplacian matrix and signless Laplacian matrix of bipartite graphs are the same. This is a generalization of the characteristic polynomial for Laplacian matrix and signless Laplacian matrix of bipartite graphs. Furthermore, we consider the relations between the characteristic polynomial and the immanantal polynomial for trees. [ABSTRACT FROM AUTHOR]

We study the equivalence between bipartiteness and symmetry of spectra of mixed graphs, for θ -Hermitian adjacency matrices defined by an angle θ ∈ (0 , π ]. We show that this equivalence holds when, for example, an angle θ is an algebraic number, while it breaks down for any angle θ ∈ Q π. Furthermore, we construct a family of non-bipartite mixed graphs having the symmetric spectra for given θ ∈ Q π. [ABSTRACT FROM AUTHOR]

In this paper, bipartite graphs and their adjacency matrices are applied to equivalently represent covering-based rough sets through three sides, which are approximation operators, properties and reducible elements. Firstly, a bipartite graph is constructed through a covering. According to the constructed bipartite graph, two equivalent representations of a pair of covering upper and lower approximation operators are presented. And an algorithm is designed for computing the pair of covering approximation operators from the viewpoint of these equivalent representations. Some properties and reducible elements of covering-based rough sets are also investigated through the constructed bipartite graph. Finally, an adjacency matrix of the constructed bipartite graph is proposed, and reducible elements in the covering are obtained through the proposed adjacency matrix. Moreover, an equivalent representation of the covering upper approximation operator is presented through the proposed adjacency matrix. In a word, these results show two interesting views, which are graphs and matrices, to investigate covering-based rough sets. [ABSTRACT FROM AUTHOR]

A graph G is F -free, if it contains no F as a subgraph. A Brualdi-Solheid-Turán type problem asks what is the maximum spectral radius of an F -free graph of order n ? Let K a , b • K 3 denote the graph obtained by identifying a vertex of K a , b belonging to the part of size b and a vertex of K 3. In this paper, we consider about a Brualdi-Solheid-Turán type problem on non-bipartite graphs. We prove that if G is a non-bipartite graph with order n ≥ 21 and ρ (G) ≥ ρ (K ⌈ n − 2 2 ⌉ , ⌊ n − 2 2 ⌋ • K 3) , then G contains a pentagon unless G ≅ K ⌈ n − 2 2 ⌉ , ⌊ n − 2 2 ⌋ • K 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]

The energy of a graph is defined as the sum of the absolute values of all eigenvalues with respect to its adjacency matrix. Denote by Gn,m the set of all connected graphs having n vertices and m edges. Caporossi et al. [Caporossi G, Cvetkovi D, Gutman I, et al. Variable neighbourhood search for extremal graphs. 2. Finding graphs with external energy. J Chem Inf Comput Sci. 1999;39:984–996] conjectured that among all graphs in Gn,m, n ≥ 6 and n − 1 ≤ m ≤ 2(n − 2), the graphs with minimum energy are the star Sn with m−n + 1 additional edges all connected to the same vertices for m ≤ n + ⌊ (n − 7) / 2 ⌋ , and the bipartite graph with two vertices on one side, one of which is connected to all vertices on the other side, otherwise. In this paper, we provide a new approach to investigate the conjecture above. Especially, we determine the unique tetracyclic graph having minimum energy. [ABSTRACT FROM AUTHOR]

Let A(G) and D(G) be the adjacency matrix and the diagonal matrix with outdegrees of vertices of a digraph G, respectively. In 2017, Nikiforov proposed to study the convex combinations of the adjacency matrix and diagonal matrix of the degrees of undirected graphs. In 2019, Liu et al. extended the definition to digraphs. For any real α ∈ [0,1], the matrix Aα(G) of a digraph G is defined as Aα(G) = αD(G)+(1−α)A(G). The largest modulus of the eigenvalues of Aα(G) is called the Aα spectral radius of G, denoted by λα(G). This paper proves some extremal results about the Aα spectral radius λα(G) that generalize previous results about λ0(G) and λ1/2 (G). We mainly characterize the extremal digraph with the maximum (or minimum) Aα spectral radius among all ∞-digraphs and θ-digraphs on n vertices. Furthermore, we determine the digraphs with the second and the third minimum Aα spectral radius among all strongly connected bicyclic digraphs. For 0 ≤ α ≤ 1 2, we also determine the digraphs with the second, the third and the fourth minimum Aα spectral radius among all strongly connected digraphs on n vertices. Finally, we characterize the digraph with the minimum Aα spectral radius among all strongly connected bipartite digraphs which contain a complete bipartite subdigraph. [ABSTRACT FROM AUTHOR]

Chain graphs and threshold graphs play a very important role in Spectral Graph Theory, since the maximizers for the largest eigenvalue of the adjacency matrix (for graphs of fixed order and size, either connected or disconnected) belong to these classes (threshold graphs in the general case, and chain graphs in the bipartite case). Nesting in the neighborhood of vertices in these graphs has gained the attention of various researchers. Motivated by this structure, we generalize and define a new class of graphs named it as 'partial threshold graphs' and study the properties. In this article, we give bounds and expressions for the Wiener index and Hyper-Wiener index of a partial threshold graph. We extend the study further and give a set of integers, except which every other integer is the Wiener index of some partial threshold graph. The highlight of the article is an algorithm for the inverse Wiener index problem of partial threshold graphs. [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]

The trace norm of a digraph D is the trace norm of its adjacency matrix A (i.e. the sum of the singular values of A). In particular, when G is a graph then its trace norm is the well-known energy of G introduced by I. Gutman in 1978. In this paper, we address the following problem: among all orientations of a given bipartite graph, which has minimal trace norm? We show that the minimal trace norm is attained in sink-source orientations (i.e. orientations in which every vertex is a sink vertex or a source vertex). Consequently, if is a set of connected bipartite graphs with minimal energy G, then the sink-source orientations of G have minimal trace norm among all orientations of graphs in. This is a consequence of our main result which relates the energy of a graph with the trace norm of its orientations. As another application we find the extremal values of the trace norm among all orientations of unicyclic graphs. [ABSTRACT FROM AUTHOR]

Let G be a bipartite graph with adjacency matrix A. If G has a unique perfect matching, then A has an inverse A1 which is a symmetric integral matrix, and hence the adjacency matrix of a multigraph. The inverses of bipartite graphs with unique perfect matchings have a strong connection to Möbius functions of posets. In this note, we characterize all bipartite graphs with a unique perfect matching whose adjacency matrices have inverses diagonally similar to non-negative matrices, which settles an open problem of Godsil on inverses of bipartite graphs in [Godsil, Inverses of Trees, Combinatorica 5 (1985) 33-39]. [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]

Clustering bipartite graphs is a fundamental task in network analysis. In the high-dimensional regime where the number of rows |$n_{1}$| and the number of columns |$n_{2}$| of the associated adjacency matrix are of different order, the existing methods derived from the ones used for symmetric graphs can come with sub-optimal guarantees. Due to increasing number of applications for bipartite graphs in the high-dimensional regime, it is of fundamental importance to design optimal algorithms for this setting. The recent work of Ndaoud et al. (2022, IEEE Trans. Inf. Theory, 68, 1960–1975) improves the existing upper-bound for the misclustering rate in the special case where the columns (resp. rows) can be partitioned into |$L = 2$| (resp. |$K = 2$|⁠) communities. Unfortunately, their algorithm cannot be extended to the more general setting where |$K \neq L \geq 2$|⁠. We overcome this limitation by introducing a new algorithm based on the power method. We derive conditions for exact recovery in the general setting where |$K \neq L \geq 2$|⁠ , and show that it recovers the result in Ndaoud et al. (2022, IEEE Trans. Inf. Theory, 68, 1960–1975). We also derive a minimax lower bound on the misclustering error when |$K=L$| under a symmetric version of our model, which matches the corresponding upper bound up to a factor depending on |$K$|⁠. [ABSTRACT FROM AUTHOR]

Complex networks can often exhibit a high degree of bipartivity. There are many well-known ways for testing this, and in this article, we give a systematic analysis of characterizations based on the spectra of the adjacency matrix and various graph Laplacians. We show that measures based on these characterizations can be drastically different results and leads us to distinguish between local and global loss of bipartivity. We test several methods for finding approximate bipartitions based on analysing eigenvectors and show that several alternatives seem to work well (and can work better than more complex methods) when augmented with local improvement. [ABSTRACT FROM AUTHOR]

Heterogeneous information networks (HIN), containing different types of entities with various kinds of interaction relations in between, provide richer information than homogeneous networks. Heterogeneous motifs are induced structural subgraph patterns with semantic in HINs. There has been many works using motifs to participate in the representation learning of HINs, but rarely to understand the respective influences of motifs. Due to the rich semantic information contained in heterogeneous motifs, the effects of different structures are inconsistent in network representation. In this paper, we introduce a case study on AMiner dataset, by extracting the heterogeneous motifs with various types of nodes and edges, especially four-node motifs, the relations between those motifs also are explored. During the study process, we first construct a set of motif instances identified by subgraph isomorphism algorithm as a weighted bipartite graph and then use another semantically related node type to extract target node features from pruned adjacency matrix. Next, a series of experiments are designed to evaluate the effect of each motif and the irrelevance of different motifs. Experimental results show that embeddings by our framework achieves excellent results compared with several state-of-the-art alternatives in node classification and clustering tasks. [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]

Let G be a graph of order n with adjacency matrix A(G) and diagonal matrix of degree D(G). For every α ∈ [ 0 , 1 ] , Nikiforov (Appl Anal Discrete Math 11(1):81–107, 2017) defined the matrix A α (G) = α D (G) + (1 - α) A (G) . In this paper, we present the A α (G) -characteristic polynomial when G is obtained by coalescing two graphs, and if G is a semi-regular bipartite graph we obtain the A α -characteristic polynomial of the line graph associated with G. Moreover, if G is a regular graph, we exhibit the A α -characteristic polynomial for the graphs obtained from some operations. [ABSTRACT FROM AUTHOR]