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]

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]

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 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, 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]

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]

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]

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]

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]

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]

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]

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]

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 construct a graph-theoretic model for Jacobsthal and Jacobsthal-Lucas numbers. As byproducts, we then develop addition formulas for the Jacobsthal family. [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]

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]

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]

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]