Search

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]

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]

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]

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]

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]

A graph G is called H -free, if it does not contain H as a subgraph. In 2010, Nikiforov proposed a Brualdi-Solheid-Turán type problem: what is the maximum spectral radius of an H -free graph of order n ? In this paper, we consider the Brualdi-Solheid-Turán type problem for non-bipartite graphs. Let K a , b • K 3 denote the graph obtained by identifying a vertex of K a , b in the part of size b and a vertex of K 3. We prove that if G is a non-bipartite graph of order n satisfying ρ (G) ≥ ρ (K ⌈ n − 2 2 ⌉ , ⌊ n − 2 2 ⌋ • K 3) , then G contains all odd cycles C 2 l + 1 for each integer l ∈ [ 2 , k ] unless G ≅ K ⌈ n − 2 2 ⌉ , ⌊ n − 2 2 ⌋ • K 3 , provided that n is sufficiently large with respect to k. This resolves the problem posed by Guo, Lin and Zhao (2021). [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]

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]

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]

Given a graph G . The fewest number of vertices whose deletion yields a bipartite graph from G was defined by S. Fallat and Yi-Zheng Fan to be the vertex bipartiteness of G and it is denoted by υ b ( G ) . We consider the set Σ k ( n ) defined by { G = ( V ( G ) , E ( G ) ) : G connected , | V ( G ) | = n and υ b ( G ) ≤ k } . In this work we identify the graph in Σ k ( n ) with maximum spectral radius and maximum signless Laplacian spectral radius. [ABSTRACT FROM AUTHOR]

With a nonzero rectangular ( 0 , 1 ) -matrix A we associate an undirected graph G A that corresponds to the linear transformation X ↦ A X T A . We use the generalized singular-value decomopsition of incidence matrices to count the number of connected components and the number of bipartite connected components of G A . We show that G A is connected if and only if G A has no bipartite connected component or isolated vertex. We also show that if A has no row or column of 0's, then the number of connected components is 1 2 s ( s + 1 ) and the number of bipartite connected components is 1 2 s ( s − 1 ) , where s is the number of chainable components of A , that is, the number of connected components in the undirected graph with adjacency matrix ( O A A T O ) . [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]

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]

Let k , p , q be positive integers with k < p < q + 1 . We prove that the maximum spectral radius of a simple bipartite graph obtained from the complete bipartite graph K p , q of bipartition orders p and q by deleting k edges is attained when the deleted edges are all incident on a common vertex which is located in the partite set of order q . Our method is based on new sharp upper bounds on the spectral radius of bipartite graphs in terms of their degree sequences. [ABSTRACT FROM AUTHOR]

In this article, we construct bipartite graphs which are cospectral for both the adjacency and normalized Laplacian matrices using the notion of partitioned tensor products. This extends the construction of Ji, Gong, and Wang [9]. Our proof of the cospectrality of adjacency matrices simplifies the proof of the bipartite case of Godsil and McKay's construction [4] , and shows that the corresponding normalized Laplacian matrices are also cospectral. We partially characterize the isomorphism in Godsil and McKay's construction, and generalize Ji et al.'s characterization of the isomorphism to biregular bipartite graphs. The essential idea in characterizing the isomorphism uses Hammack's cancellation law as opposed to Hall's marriage theorem used by Ji et al. [ABSTRACT FROM AUTHOR]

Let G be a graph on n vertices and λ 1 , λ 2 , ... , λ n its eigenvalues. The Estrada index of G is an invariant that is calculated from the eigenvalues of the adjacency matrix of a graph. In this paper, we present some new lower bounds for the Estrada index of graphs and in particular of bipartite graphs that only depend on the number of vertices, the number of edges, Randić index, maximum and minimum degree and diameter. [ABSTRACT FROM AUTHOR]