Search

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]

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]

The class of unicyclic non-bipartite graphs with unique perfect matching, denoted by U , is considered in this article. This article provides a complete characterization of unicyclic graphs in U which possess tricyclic inverses. [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]

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]

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]

A cograph is a simple graph which contains no path on 4 vertices as an induced subgraph. We consider the eigenvalues of adjacency matrices of cographs and prove that a graph G is a cograph if and only if no induced subgraph of G has an eigenvalue in the interval. It is also shown that the multiplicity of any eigenvalue of a cograph G does not exceed the sum of multiplicities of 0 and as eigenvalues of G. We introduce a partial order on the vertex set of graphs G in terms of inclusions among the open and closed neighbourhoods of vertices, and conjecture that the multiplicity of any eigenvalue of a cograph G except for does not exceed the maximum size of an antichain with respect to that partial order. In two extreme cases (in particular for threshold graphs), the conjecture is shown to be true. Finally, we prove that bipartite -free graphs have no eigenvalue in the intervals and (0, 1 / 2). [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]

The k-th power of a graph G, denoted by [ABSTRACT FROM AUTHOR]

A graphis nonsingular if its adjacency matrixis nonsingular. A nonsingular graphis said to have an inverseifis signature similar to a nonnegative matrix. An-graphis a bipartite graph with a unique perfect matching. We introduce the ‘even’ness of a nonmatching edge and show that under certain conditions a connected-graph has an inverse if and only ifis bipartite, whereis the set of all even nonmatching edges. This extends some known results, providing us with a larger class of graphs possessing inverses. [ABSTRACT FROM PUBLISHER]

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]

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]